LeetCode 30.串联所有单词的子串

30.串联所有单词的子串

思考：就是动态处理n个长度为m的字符串，用map去存储遇见的字符串的状态，只有为0的时候才是匹配成功，然后从mp里erase掉该键值对。当mp为空时，就是成功匹配。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int lens=s.size();
        int n=words.size();
        int m=words[0].size();
        vector<int> v;
        for(int i=0;i<m&&i<lens;i++){//遍历前m个，是因为后面的内容都是重复的
            unordered_map<string, int> mp;//用于存储遇见的字符出现的次数
            for(int j=0;j<n;j++){//先把words里的字符都存进去+1
                mp[words[j]]++;
            }

            for(int j=0;j<n&&i+n*m<=lens;j++){//然后处理i位置开始的n个长度为m的字符串
                mp[s.substr(i+j*m,m)]--;//把这n个字符串在mp里面-1
                if(mp[s.substr(i+j*m,m)]==0)//当为0的时候，在mp里删除该键值对
                    mp.erase(s.substr(i+j*m,m));
            }

            for(int j=i;j+n*m<=lens;j+=m){//这个就是动态处理n个字符串
                if(j!=i){//当不是从i开始的n个字符串时
                    mp[s.substr(j+(n-1)*m,m)]--;//就加入一个新的字符串
                    if(mp[s.substr(j+(n-1)*m,m)]==0) mp.erase(s.substr(j+(n-1)*m,m));//当为0的时候，在mp里删除该键值对
                    mp[s.substr(j-m,m)]++;//删掉最前面的字符串
                    if(mp[s.substr(j-m,m)]==0) mp.erase(s.substr(j-m,m));//当为0的时候，在mp里删除该键值对
                }
                if(mp.empty()){//这里就是判断遇见的字符串是否都成功匹配到，匹配到就会用erase()消除掉
                    v.push_back(j);
                }
            }

        }
        return v;
    }
};
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
35