LeetCode 30 Substring with Concatenation of All Words

LeetCode 30 Substring with Concatenation of All Words

Description

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

解题思路

代码来自评论区。
所有的单词长度相同，这是一个重要的条件，使得滑动窗口的想法成为可能。通过map来记录出现的单词。

代码

class Solution{
public:
    // travel all the words combinations to maintain a window
// there are wl(word len) times travel
// each time, n/wl words, mostly 2 times travel for each word
// one left side of the window, the other right side of the window
// so, time complexity O(wl * 2 * N/wl) = O(2N)
    vector<int> findSubstring(string s, vector<string> &words) {
        vector<int> ans;
        auto n = (int)s.size(), cnt = (int)words.size();
        if (n <= 0 || cnt <= 0) return ans;

        // init word occurence
        unordered_map<string, int> dict;
        for (int i = 0; i < cnt; ++i) dict[words[i]]++;

        // travel all sub string combinations
        auto wordLen = (int)words[0].size();
        for (int i = 0; i < wordLen; ++i) {
            int left = i, count = 0;
            unordered_map<string, int> tdict;
            for (int j = i; j <= n - wordLen; j += wordLen) {
                string str = s.substr(j, wordLen);
                // a valid word, accumulate results
                if (dict.count(str)) {
                    tdict[str]++;
                    if (tdict[str] <= dict[str])
                        count++;
                    else {
                        // a more word, advance the window left side possiablly
                        while (tdict[str] > dict[str]) {
                            string str1 = s.substr(left, wordLen);
                            tdict[str1]--;
                            if (tdict[str1] < dict[str1]) count--;
                            left += wordLen;
                        }
                    }
                    // come to a result
                    if (count == cnt) {
                        ans.push_back(left);
                        // advance one word
                        tdict[s.substr(left, wordLen)]--;
                        count--;
                        left += wordLen;
                    }
                }
                    // not a valid word, reset all vars
                else {
                    tdict.clear();
                    count = 0;
                    left = j + wordLen;
                }
            }
        }
        return ans;
    }
};