30. 串联所有单词的子串

[zpc7]

30. 串联所有单词的子串

参考题解: https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solution/chuanlian-by-jiang-hui-4-ycgi/

代码 TS

function findSubstring(s: string, words: string[]): number[] {
    const res: number[] = [];

    const n: number = words.length; //单词个数
    const wordLength: number = words[0].length; // 单个单词的长度
    const strLength: number = s.length;  // 字符串的长度
    const substringLength: number = wordLength * n; // 需要查找的子串的长度

    const wordsMap = new Map<string, number>(); // 存储所有单词(这里的单词也可能重复)

    for (const word of words) {
        wordsMap.set(word, (wordsMap.get(word) || 0) + 1)
    }

    for (let i = 0; i < strLength - substringLength + 1; i++) {
        let curMap = new Map<string, number>();
        // 是否存在异常情况
        let errorFlag = false;
        for (let j = 0; j < n; j++) {
            //第j个单词
            const curWord = s.substring(i + j * wordLength, i + (j + 1) * wordLength);
            //出现不存在单词
            if (!wordsMap.has(curWord)) {
                errorFlag = true;
                break;
            }
            // 否则将这个单词存储在map
            curMap.set(curWord, (curMap.get(curWord) || 0) + 1);
            //出现超数量单词
            if (curMap.get(curWord) > wordsMap.get(curWord)) {
                errorFlag = true;
                break;
            }
        }
        //没有异常情况 记录答案
        if (!errorFlag) {
            res.push(i);
        }
    }
    return res;
};