Monday, November 25, 2013

LeetCode Problem : Substring with Concatenation of All Words

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"barfoothefoobarman"
L["foo", "bar"]
You should return the indices: [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