數組Leetcode解決方案中的字符串匹配


難度級別 容易獎學金
經常問 亞馬遜

數組Leetcode解決方案中的字符串匹配問題為我們提供了一個字符串數組。 問題要求我們找到屬於其他子字符串的字符串 從輸入。 提醒一下,子字符串不過是從兩端刪除字符後剩下的一部分字符串。 您也可以從兩端刪除0個字符。 並且刪除的字符數不必相同。 因此,為了更好地理解,讓我們看一些示例。

數組Leetcode解決方案中的字符串匹配

words = ["mass","as","hero","superhero"]
["as","hero"]

說明:輸出具有“ as”,因為它來自“ mass”。 同樣,“英雄”是“超級英雄”的一部分。 因此,我們只是找到了也是輸入的輸入的子字符串。

words = ["leetcode","et","code"]
["et","code"]

說明:此示例顯示子字符串可以來自同一字符串。 像這裡一樣,輸出中的兩個字符串都是“ leetcode”的子字符串。

數組Leetcode解決方案中的字符串匹配方法

問題要求我們從輸入中挑選出滿足特定條件的字符串。 條件是該字符串應該是同樣在輸入中的字符串的子字符串。 因此,我們嘗試模擬此過程,以查找作為其他字符串的子字符串的字符串。 剩下的唯一複雜之處就是實現。 因此,我們使用哈希集或無序映射來跟踪將用作輸出的字符串。 我們使用兩個嵌套循環來檢查ith索引處的字符串是否是jth索引處的字符串的子字符串,反之亦然。 在C ++中,我們創建了自己的函數,該函數檢查第二個字符串是否是第一個參數的子字符串。 在Java中,可以使用contains()函數輕鬆找到它。

數組Leetcode解決方案中用於字符串匹配的代碼

C ++代碼

#include <bits/stdc++.h>
using namespace std;

bool isSubstr(string a, string b){
    int n = a.size(), m = b.size();
    for(int i=0;i<=n-m;i++){
        if(a.substr(i, m) == b)
            return true;
    }
    return false;
}

vector<string> stringMatching(vector<string>& words) {
    unordered_set<string> tmp;
    int n = words.size();
    for(int i=0;i<n-1;i++){
        string curWord = words[i];
        for(int j=i+1;j<n;j++){
            string nextWord = words[j];
            if(isSubstr(curWord, nextWord))
                tmp.insert(nextWord);
            if(isSubstr(nextWord, curWord))
                tmp.insert(curWord);
        }
    }
    return vector<string>(tmp.begin(), tmp.end());
}

int main(){
    vector<string> input({"mass","as","hero","superhero"});
    vector<string> v = stringMatching(input);
    for(auto x: v)
        cout<<x<<" ";
}
hero as

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> stringMatching(String[] words) {
        HashSet<String> tmp = new HashSet<>();
        
        int n = words.length;
        for(int i = 0; i<n-1; i++) {
            String curWord = words[i];
            for(int j = i+1; j<n; j++) {
                String nextWord = words[j];
                if(curWord.contains(nextWord))
                    tmp.add(nextWord);
                if(nextWord.contains(curWord))
                    tmp.add(curWord);
            }
        }
        
        return new ArrayList<String>(tmp);
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String[] words = {"mass","as","hero","superhero"};
    List<String> list = stringMatching(words);
    for(String x: list)
      System.out.print(x+" ");
  }
}
hero as

複雜度分析

時間複雜度

O(N ^ 2 * | S |), 因為我們使用了兩個嵌套循環,它們取決於輸入字符串的數量。 然後該函數用於查找字符串是否為其他需要的子字符串 O(| S |) 時間。

空間複雜度

上), 在最壞的情況下,整個輸入可以是輸出。 因此,空間複雜度是線性的。