【Day 23 】2021-06-01 - 30. 串联所有单词的子串

题目描述

入选理由

1. hashtable 用于空间换时间

题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时空复杂度

时间复杂度：O(n*k) s.length * words.length

空间复杂度: O(n) 2 个 Map 的空间 N 最大为 words.length

果然困难题最难的是理解题意

var findSubstring = function (s, words) {
    let wordLength = words[0].length
    const result = []
    let memo = new Map()
    for (let i = 0; i < words.length; i++) {
        const word = words[i]
        memo.set(word, (memo.get(word) || 0) + 1)
    }
    for (let i = 0; i < s.length; i ++) {
        let map = new Map(memo)
        let wordCount = words.length
        for (let j = i; j < s.length; j += wordLength) {
            const word = s.slice(j, j + wordLength)
            if (!map.get(word)) break
            const count = map.get(word)
            map.set(word, count - 1)
            wordCount--
            if (wordCount === 0) {
                result.push(i)
                break
            }
        }
 
    }
    return result
};

参考回答

• 官方题解