LeetCode 题解——Substring with Concatenation of All Words

发表于 | 分类于 | 阅读次数:
字数统计: 576 字

LeetCode 题解——Substring with Concatenation of All Words

题意

给定一个字符串，和一组匹配字符串（vector），其中每一个字符串的长度是相同的，后面的这一组字符串可以形成一个组合，比如[“ab”,”cd”]可以组合成的字符串有：”abcd” “cdab”。题目要求我们在给定的这个字符串中查找出现后面这些组合的子串的位置（给出首字母位置）

题解

题目中给出的匹配字符串组中每一个字符串的长度是相同的这个条件降低了题目的难度，如果从普通的字符串匹配的思路下手的话，就是每次从原串截取对比的长度是一样的，然后截取的字符串可以分割成几个长度相同的子字符串，我们只要判断这几个字符子串是否都在给出的这组匹配字符串中就行了。

这里使用两个unordered_map(Hash实现，性能更优)来判断是否都在这组字符串中，第一个map存储匹配字符串组中的字符串和出现的次数（都是1），第二个map存储截取的字符串分割以后的子串（并且在匹配字符串组中）以及其出现的次数，如果其次数大于1，表示截取的这段不符合条件，进行下一次匹配。

map有两个作用：查找字符串；记录出现次数

代码

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
36
37
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        // 用来进行对比的map
        unordered_map<string, int> contrast;
        for(string s : words)
        {
            contrast[s]++;
        }
        int slen = s.length(), wlen = words[0].length(), wsize = words.size();
        // 依次截取一定长度的字符串进行匹配
        for(int i=0; i<slen-wsize*wlen+1; i++)
        {
            unordered_map<string, int> tem;
            int j=0;
            for(; j<wsize; j++)
            {
                // 分割以后的每一个字符串
                string stem = s.substr(i+j*wlen, wlen);
                // 判断是否在匹配字符串组中
                if(contrast.find(stem) != contrast.end())
                {
                    tem[stem]++;
                    // 出现次数超过1，放弃
                    if(tem[stem] > contrast[stem])
                        break;
                }
                else
                    break;
            }
            if(j == wsize)
                res.push_back(i);
        }
        return res;
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目