substring-with-concatenation-of-all-words

题目:

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S:”barfoothefoobarman”
L:[“foo”, “bar”]
You should return the indices:[0,9].
(order does not matter).

程序：

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        map<string, int> dict;
        vector<int> res;
        if (!S.size() || !L.size())
            return res;
        for (int i = 0; i < L.size(); i++)
            dict[L[i]] ++;

        int m = L.size();
        int n = L[0].size();
        int size = m*n;
        for (int i = 0; i < S.size() - size + 1; i++)
        {
            for (int a = 0; a < m; a++)//字典归0
            {
                dict[L[a]] = 0;
            }
            for (int a = 0; a < m; a++)//与上步一起初识化字典
            {
                dict[L[a]] ++;
            }
            string s = S.substr(i, size);
            int j = 0;
            while (j < m)
            {

                string ss = s.substr(j*n, n);
                if (dict.find(ss) != dict.end())
                    dict[ss]--;
                else
                    break;
                j++;
            }

            if (j != m)
                continue;
            int k = 0;
            for (; k < m; k++)
            {
                if (dict[L[k]])
                    break;
            }

            if (k == m)
                res.push_back(i);
        }

        return res;
    }
};
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

点评：

通过哈希表减少时间复杂度