hard题记录30

题目描述

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

Output: []

Explanation:

There is no concatenated substring.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

Output: [6,9,12]

Explanation:

The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"]. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"]. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

思路

用滑动窗口，每次滑倒可能的排列时就添加下标。由于words中每个词的大小都相同，遍历时就可以一次跳一个词。对于每个窗口，检查内部的东西是否符合要求。检查的细节如下：

使用两个hashmap，第一个 originalCount 记录words中每个单词的数量，第二个currentCount记录当前窗口中每个单词的数量。每移动到一个新单词时，先检查它在不在 originalCount ，如果是，放进currentCount，如果不是，可以直接把窗口挪到这个词末尾（反正它附近不可能有有效排列）。要实现这一点还需要一个变量count记录窗口中有效单词的数量。只有count是最大值时，这个窗口才有可能是有效的，否则直接跳。

如果在一个窗口内遇到多次重复单词（比words多），就从左边缩短窗口。

考虑第一个词就无效的情况。如果序列中有一个无效前缀，它的长度可能在0到单词长度-1之间（当然可能更长，但由于滑动窗口每次跳一整个词，取余后只需考虑0到单词长度-1的情况），所以最外层循环要进行k（单词长度）次，以避免无效前缀的影响。

在每层大循环内，遍历序列的复杂度是O(N)，所以最终复杂度O(N*k)。

核心思想在于“只计数而不考虑具体字符”。

完整代码

function findSubstring(s: string, words: string[]): number[] {
    let wordSize = words[0].length;
    let wordCount = words.length;
    let n = s.length;
    let result: number[] = [];

    // string: number，记录单词个数
    let originalCount: Map<string, number> = new Map();

    // 特殊情况直接返回空表
    if(wordCount === 0 || n === 0) return [];

    // 初始化单词个数表
    for(let word of words) {
        originalCount.set(word, (originalCount.get(word) ?? 0) + 1);
    }

    // 用偏移量跳过可能的无效前缀
    for(let offset = 0; offset < wordSize; offset++) {
        // 每一轮内循环都维护一个新map
        let currentCount: Map<string, number> = new Map();
        let start = offset;
        let count = 0;
        // 右边界一次跳一个单词长度
        // 注意是小于等于n，否则会漏掉最后一个
        for(let end = offset; end + wordSize <= n; end += wordSize) {
            // 当前要判断的，窗口右侧第一个单词
            let currentWord = s.substring(end, end+wordSize);
            if(originalCount.has(currentWord)) {
                // 如果第一次添加就置1，否则+1
                currentCount.set(currentWord, (currentCount.get(currentWord) ?? 0) + 1);
                count++;

                // 此时尚未移动右边界。如果窗口内单词数量超了，窗口左边界往右挪一个单词
                while(currentCount.get(currentWord)! > originalCount.get(currentWord)!) {
                    let startWord = s.substring(start, start + wordSize);
                    currentCount.set(startWord, currentCount.get(startWord)! - 1);
                    start += wordSize;
                    count --;
                }

                if(count === wordCount) {
                    result.push(start);
                }
            } else {
                // 如果这个词根本不在words里，直接把左边界挪到它右边
                count= 0;
                start = end + wordSize;
                currentCount.clear();
            }
        }
    }
    return result;
};

console.log(findSubstring("barfoofoobarthefoobarman", ["bar","foo","the"]));