1408. String Matching in an Array

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = list()
        words = sorted(words, key = len)
        for i in range(len(words)):
            for j in range(i+1, len(words)):
                if words[i] in words[j]:
                    ans.append(words[i])
                    # 只加入一次
                    break
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isValid(string &a, string &b){
        int n = a.size(), m=b.size();
        for(int i=0;i<=m-n;++i){
            int count = 0;
            for(int j=0;j<n;++j){
                if(a[j]!=b[i+j]) break;
                else count++;
            }
            if( count ==n) return true;
        }
        return false;
    }
    vector<string> stringMatching(vector<string>& words) {
        vector<string> ret;
        int n = words.size();
        sort(words.begin(), words.end(), [](string &a, string &b){
            return a.size()<b.size();
        });
        for(int i=0;i<n;++i){
            for(int j = i+1;j<n;++j){
                if (isValid(words[i], words[j])){
                    ret.push_back(words[i]);
                    break;
                }
            }
        }
        return ret;
    }
};

analysis

  • time complexity O(n^3)
  • space complexity O(n)