30.md

30 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]

解题

解法一 递归

const findSubstring = (s, words) => {
    if (!s || words.length === 0) return [];
    let combinedWords = []
    const num = words.length;
    const findWordsCombine = (range, _arr) => {
        return range.length === num ? combinedWords.push(range) : _arr.forEach((item, index) => {
            const temp = [..._arr];
            temp.splice(index, 1)
            findWordsCombine(range.concat(item), temp)
        });
    }
    findWordsCombine([], words)
    return Array.from(new Set(combinedWords.reduce((last, item) => {
        const findStartIndex = (str, target) => {
            const idxs = [];
            let position = str.indexOf(target);
            while (position > -1) {
                idxs.push(position);
                position = str.indexOf(target, position + 1);
            }
            return idxs
        }
        return [...last, ...findStartIndex(s, item.join(""))]
    }, []).filter(item => item != -1)))
};

解法二

const findSubstring = (s, words) => existStrIdx(s, words, words.length > 0 ? words[0].length : 0)

const existStrIdx = (s, words, len) => {
    let result = []
    if (len) {
        const wordsLen = len * words.length;
        const wordsMap = initWordsMap(words);
        for (let i = 0; i <= s.length - wordsLen; i++) {
            const subs = s.substr(i, wordsLen);
            initStringMap(subs, len, wordsMap)
            if (compare(wordsMap)) {
                result.push(i)
            }
        }

    }
    return result
}
const initWordsMap = words => {
    let map = {}
    for (let word of words) {
        if (map[word]) {
            map[word].count += 1
        } else {
            map[word] = { count: 1 }
        }
    }
    return map
}
const initStringMap = (s, len, wordsMap) => {
    for (let i = 0; i < s.length; i += len) {
        let field = s.substr(i, len)
        if (wordsMap[field]) {
            if (wordsMap[field].nowCount) {
                wordsMap[field].nowCount += 1
            } else {
                wordsMap[field].nowCount = 1
            }
        }
    }
}
const compare = (wordsMap) => {
    const keys = Object.keys(wordsMap);
    let lock = true
    for (let i = 0; i < keys.length; i++) {
        const { count, nowCount } = wordsMap[keys[i]];
        wordsMap[keys[i]].nowCount = 0;
        if (count != nowCount) {
            lock = false
        }
    }
    return lock
}