Problem
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).
[0,9]
.(order does not matter).
Code
vector<int> findSubstring(string S, vector<string> &L) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<int> result; int m = L.size(); if(m == 0) return result; map<string,int> words; vector<string>::const_iterator it = L.begin(); for(;it != L.end();++it) words.insert(make_pair(*it,0)); it = L.begin(); for(;it != L.end();++it) ++words[*it]; int len = L[0].size(); int n = S.size(); for(int i = 0;i <= n - m*len;++i){ string text = S.substr(i,m*len); map<string,int> wordmap; int j = 0; for(;j < m;++j){ string word = text.substr(j*len,len); if(words.find(word) == words.end()) break; ++wordmap[word]; if(wordmap[word] > words[word]) break; } if(j == m){ result.push_back(i); } } return result; }
No comments:
Post a Comment