[LeetCode] 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).

» Solve this problem

[解题思路]
没想出什么太好的办法，猜测这题应该是一道实现题。用两个map来统计字符串的出现次数，然后从左往右扫描主字符串。


[Code]

1:    vector<int> findSubstring(string S, vector<string> &L) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      map<string, int> expectCount;  
5:      map<string, int> realCount;  
6:      for(int i =0; i< L.size(); i++)  
7:      {  
8:        expectCount[L.at(i)]++;  
9:      }  
10:      vector<int> result;  
11:      int row = L.size();  
12:      if(row ==0) return result;  
13:      int len = L[0].size();  
14:      for(int i =0; i< (int)S.size() - row*len+1; i++)  
15:      {  
16:        realCount.clear();  
17:        int j =0;  
18:        for(; j< row; j++)  
19:        {  
20:          string sub = S.substr(i+j*len, len);  
21:          if(expectCount.find(sub) != expectCount.end())  
22:          {  
23:            realCount[sub]++;  
24:          }  
25:          else  
26:            break;  
27:          if(realCount[sub] > expectCount[sub])  
28:          {  
29:            break;  
30:          }  
31:        }  
32:        if(j == row)  
33:          result.push_back(i);  
34:      }  
35:      return result;  
36:    }  

[注意]
Line 14 红字部分。如果S.size()是unsigned int，如果不先转换为int的话，计算结果会被promote成unsigned int。 比如 (unsigned int) 1 - (int)2, 最后的结果不是-1，而是4294967295。