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:
L:
S:
"barfoothefoobarman"
L:
["foo", "bar"]
You should return the indices:
(order does not matter).
» Solve this problem[0,9]
.(order does not matter).
[解题思路]
没想出什么太好的办法,猜测这题应该是一道实现题。用两个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:
1 sec on Large Judge (java):
https://github.com/leoyonn/leetcode/blob/master/src/q029_substring_of_all_words/Solution.java
Post a Comment