凌云的博客

LeetCode 算法题 30. Substring with Concatenation of All Words

分类：algorithm| 发布时间：2016-08-07 21:48:00

---

题目

You are given a string, s, and a list of 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).

题意

给出一个字符串以及一组长度相同的单词，找出所有每个单词连接而成的字串的下标。

解法 1

这种解法的基本思路是将给出的 words 中每个单词出现的次数放入一个 map 中。 然后取出给定的字符串的 num * len 个字符，分为 num 个单词， 将其出现的次数放入另一个 map 中，对比这两个 map 是否相同。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> counts;
        for (const string &word: words) counts[word]++;
        int n = s.length(), num = words.size(), len = words[0].length();
        vector<int> indexes;
        for (int i = 0; i < n - num * len + 1; i++) {
            unordered_map<string, int> seen;
            int j = 0;
            for (; j < num; j++) {
                string word = s.substr(i + j * len, len);
                if (counts.find(word) != counts.end()) {
                    seen[word]++;
                    if (seen[word] > counts[word])
                        break;
                } else {
                    break;
                }
            }

            if (j == num) indexes.push_back(i);
        }

        return indexes;
    }
};

解法 2

这个算法可以看成是上一个算法经过优化得到的。 首先，外层循环 i 从 0 到 wl。 相应地，内层循环以 wl 为单位处理整个字符串。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;

        int n = s.size(), cnt = 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
        int wl = words[0].size();
        for (int i = 0; i < wl; ++i) {
            int left = i, count = 0;
            unordered_map<string, int> tdict;
            for (int j = i; j <= n - wl; j += wl) {
                string str = s.substr(j, wl);

                // 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, wl);
                            tdict[str1]--;
                            if (tdict[str1] < dict[str1]) count--;
                            left += wl;
                        }
                    }

                    // come to a result
                    if (count == cnt) {
                        ans.push_back(left);
                        // advance one word
                        tdict[s.substr(left, wl)]--;
                        count--;
                        left += wl;
                    }
                } else {
                    // not a valid word, reset all vars
                    tdict.clear();
                    count = 0;
                    left = j + wl;
                }
            }
        }

        return ans;
    }
};