30. Substring with Concatenation of All Words

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

分析

从s里面，找出由words里面的所有单词组成的字符子串（每个字符串仅出现一次），不要关注顺序。

该题和 3.Longest Substring Without Repeatition 类似，都是维护一个窗口去滑动，记左边界 left，右边界right

s长度 N

words里单个单词长度 M，words单词总数 L

那么对s遍历的右边界 last = N - M + 1

在 hashmap 中存入 words 中的每个单词，key是单词，value单词出现在words中的index。 O(L)

创建一个二维数组 table [2][L]

0行：记录words中每个单词出现的次数。 O(L)

1行：记录扫描时候，left和right之间窗口中，包含words的单词出现次数

创建一个一维数组 smapping，遍历s，记录每个单词是否在 workds中。如果存在，则放入在words中的index；如果不存在，则为-1。 O(N)

算法GIF解释：

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int N = s.size();
        int M = words[0].size();
        int L = words.size();
        int last = N - M + 1;
        vector<int> result;
        unordered_map<string, int> mapping;
        vector<vector<int>> table(2,vector<int> (L));
 
        vector<int> smapping(last, -1);
 
        int index = 0, failures = 0;
        for (int i = 0; i < L; ++i) {
            auto word = mapping.find(words[i]);
            if (word == mapping.end()) {
                failures++;
                mapping.insert({ words[i], index++ });
                word = mapping.find(words[i]);
            }
            table[0][word->second]++;
        }
 
        for (int i = 0; i < last; ++i) {
            auto word = mapping.find(s.substr(i, M));
            if (word != mapping.end()) {
                smapping[i] = word->second;
            }
            else {
                smapping[i] = -1;
            }
        }
 
        for (int i = 0; i < M; ++i) {
            int currentFailures = failures;
            fill(table[1].begin(), table[1].end(), 0);
            int L = i, R = i;
            while (R < last) {
                while (currentFailures != 0 && R < last) {
                    if (smapping[R] != -1 && ++table[1][smapping[R]] == table[0][smapping[R]]) {
                        currentFailures--;
                    }
                    R += M;
                }
 
                while (currentFailures == 0 && L < R) {
                    if ((R - L) / M == words.size()) {
                        result.push_back(L);
                    }
                    if (smapping[L] != -1 && --table[1][smapping[L]] == table[0][smapping[L]] - 1) {
                        currentFailures++;
                    }
                    L += M;
                }
            }
        }
        return result;
    }
};

null

30. Substring with Concatenation of All Words

分析

代码

附件列表