Leetcode——Substring with Concatenation of All Word

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

问题描述如上

解题：

先使用一个map（C++ 11中可以使用unordered_map）来保存每个单词在words中出现的次数，注意一个单词可能会出现多次。由于每个单词的长度相同，所以扫描窗口的长度为word_size * words.size()。

首先将窗口置于s的起始位置，将窗口截成一个个word长度的串，扫描这些串是否在前面保存的map中存在，并且出现的次数相同。如果存在且相同，那么表示找到了一个match。

1class Solution {
2public:
3    vector<int> findSubstring(string s, vector<string>& words) {
4        map<string, int> record;
5        map<string, int> count;
6        vector<int> pos;
7        if (words.size() == 0)
8        {
9            return pos;
10        }
11        int word_size = (words[0]).size();
12        if (s.size() < word_size*words.size())
13        {
14            return pos;
15        }
16        
17        for (int i=0; i<words.size(); i++)
18        {
19            if (record.find(words[i]) == record.end())
20            {
21                record[words[i]] = 1;
22            }else{
23                record[words[i]]++;
24            }
25        }
26        
27        int i, j;
28        for (i=0; i< s.size()-word_size*words.size()+1 ; i++)
29        {
30            count.clear();
31            for (j=0; j<words.size(); j++)
32            {
33                string current_word = s.substr(i+j*word_size, word_size);
34                if (record.find(current_word) != record.end())
35                {
36                    if (count.find(current_word) == count.end())
37                    {
38                        count[current_word] = 1;
39                    }else{
40                        count[current_word]++;
41                    }
42                    if (count[current_word] > record[current_word])
43                    {
44                        break;
45                    }
46                }else{
47                    break;
48                }
49            }
50            if (j == words.size())
51            {
52                pos.push_back(i);
53            }
54        }
55        
56        return pos;
57    }
58};