leetcode_substring_with_concatenation_of_all_words

发表于

难度：Meidum

将目标字符串数组映射到一个hash表中，key为字符串，value为出现的次数。这里假设目标字符串数组长度为m，每个字符串的长度为n。
源字符串，从头开始遍历，检查n个字符组成的子字符串串，映射到新的hash表。如果该子字符串未在目标hash表中出现，则break；如果在目标hash表和新hash表中都出现了，且在新hash表中出现的次数已经等于目标hash表中出现的次数，则说明该字符串多了，break；如果在目标hash表中出现了，未在新hash表中出现或出现次数小于目标hash表，则将新hash表中该字符串的value+1。遍历了m次后，如果未出现break，则说明该区域的字符串是所有目标字符串的组合。

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
32
33
34
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        if(words.size()==0) return ret;
        unordered_map<string,int> to_find;
        for(string &word:words)
        {
            to_find[word]++;
        }
        
        int m = words.size();
        int n = words[0].size();
        
        for(int i = 0; i <= (int)s.size()-m*n; i++)
        {
            unordered_map<string,int> found;
            int j = 0;
            for(; j < m; j++)
            {
                string word = s.substr(i+j*n,n);
                if(to_find[word] == 0)
                    break;
                if(found[word] < to_find[word])
                    found[word]++;
                else if(found[word] >= to_find[word])
                    break;
            }
            if(j == m)
                ret.push_back(i);
        }
        return ret;
    }
};