LeetCode30 Substring with Concatenation of All Words

题目：

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 words exactly 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). （Hard）

分析：

题目意思是找到所有起始位置，使得往后的若干连续字符组成的字符串的正好是集合中所有元素组成的字符串。

自己考虑到的还是一个暴力的做法，没有超时，写起来也没那么容易。

大致思路是建一个hash存放words不同元素出现在words中的次数(开始只存放有无，后来发现words中元素可重复)

然后对s进行遍历，从每个位置开始，依次取len长度的字符串，与hash中的值比较。根据在不在hash内进行跳出循环，hash[words[j]]--等操作.

到words.size() -1 长度自然跳出循环，说明完全匹配，可以将这个i加入结果。

代码：

 1 class Solution {
 2 public:
 3     vector<int> findSubstring(string s, vector<string>& words) {
 4         int len = words[0].size();
 5         unordered_map<string, int> count;
 6         vector<int> result;
 7         if (s.size() < words.size() * len) {
 8             return result;
 9         }
10          for (int k = 0 ; k < words.size(); ++k) {
11             if (count.find(words[k]) == count.end()) {
12                 count[words[k]] = 1;
13             } 
14             else {
15                 count[words[k]] ++;
16             }
17         }
18         unordered_map<string, int> save = count;
19         for (int i = 0; i <= s.size() - words.size() * len; i++) {
20             int flag = 0;
21             for (int j = i; j < i + words.size() * len  ; j += len) {
22                 string temp = s.substr(j, len);
23                 if (count.find(temp) != count.end()) {
24                     if (count[temp] > 0) {
25                         count[temp]--;
26                     }
27                     else {
28                         flag = 1;
29                         break;
30                     }
31                 }
32                 else {
33                     flag = 1;
34                     break;
35                 }
36             }
37             if (flag == 0) {
38                 result.push_back(i);
39             }
40             count = save;
41         }
42         return result;
43     }
44 };

8月19日更新：

对于自己的实现中，每次更新i都需要拷贝一次hash表。

可以换一种方式，一个hash作为基准在循环前准备好。然后对于每个i生成一个新的hash，添加元素进去，与老的比较，比拷贝应该效率要高。

其他注意事项：

1. words.size()，s.size()都是unsigned int，所以做减法之后不会出现 -1，所以导致由此限定循环有问题，所以自己在前面加了一个

if (s.size() < words.size() * len)

搞清楚原因后前面声明两个int变量可以把这个if去掉。

2. unordered_map<string,int> hash可以直接对hash[temp]++，没有的话就是从0加1，默认初始化的0。

所以修改后的代码：

 1 class Solution {
 2 public:
 3     vector<int> findSubstring(string s, vector<string>& words) {
 4         int len = words[0].size();
 5         unordered_map<string, int> count;
 6         vector<int> result;
 7         for (int k = 0 ; k < words.size(); ++k) {
 8             count[words[k]]++;    
 9         }
10         //s.size() - words.size() * len 结果是个unsigned;
11         int n = s.size(), m = words.size();
12         for (int i = 0; i <= n - m * len; i++) {
13             unordered_map<string, int> hash;
14             int flag = 0;
15             for (int j = i; j < i + words.size() * len  ; j += len) {
16                 string temp = s.substr(j, len);
17                 hash[temp]++;
18                 if (hash[temp] > count[temp]) {
19                     flag = 1;
20                     break;
21                 }
22             }
23             if (flag == 0) {
24                 result.push_back(i);
25             }
26         }
27         return result;
28     }
29 };

好像还有个滑动窗口的解法，回头头脑清楚再研究...