[leetcode 30] Substring with Concatenation of All Words

时间:2021-02-11 06:26:34

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).

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        const int wordLength = L[0].size();
        const int length = L.size()*wordLength;
        const int n = S.size();
        vector<int> res;
        unordered_map<string, int> map;
        for (int i = 0; i < L.size(); i++) {
            ++map[L[i]];
        }
        for (int i = 0; i < n - length + 1; i++) {
            unordered_map<string, int> used(map);
            for (int j = i; j < i + length; j += wordLength) {
                auto pos = used.find(S.substr(j, wordLength));
                if (pos == used.end() || pos->second == 0) {
                    break;
                }
                if (--pos->second == 0) {
                    used.erase(pos);
                }
            }
            if (used.size() == 0) {
                res.push_back(i);
            }
            
        }
        return res;
        
    }
};