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

[解题思路]
没想出什么太好的办法,猜测这题应该是一道实现题。用两个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。



2 comments:

Unknown said...
This comment has been removed by the author.
Unknown said...

1 sec on Large Judge (java):
https://github.com/leoyonn/leetcode/blob/master/src/q029_substring_of_all_words/Solution.java