## Monday, January 7, 2013

### [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

[解题思路]

[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。