30.串联所有单词的子串.md

30. 串联所有单词的子串

给定一个字符串 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"]
输出：[]

思路

利用 hash 表。先遍历 words，把每个子串及对应的数量存储到 hash 表中。然后遍历 s，找到符合的开始节点

代码

/*

 * @lc app=leetcode.cn id=30 lang=javascript
   *
 * [30] 串联所有单词的子串
   */

// @lc code=start
/**

 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
   */
var findSubstring = function (s, words) {
  let res = [],
    len = words.length;
  if (!len) return res;
  let hash = new Map(),
    itemLen = words[0].length || 0;
  // 用hash表存储
  for (let cur of words) {
    hash[cur] = (hash[cur] || 0) + 1;
  }
  // console.log(hash);
  for (let i = 0; i < s.length - len * itemLen + 1; i++) {
    // 复制hash表
    let hasHash = {
      ...hash,
    };
    // 获取符合的子串
    for (let j = 0; j < words.length; j++) {
      const cur = s.substr(i + itemLen * j, itemLen);
      if (!hasHash[cur]) {
        break;
      } else {
        hasHash[cur]--;
        if (j === words.length - 1) {
          res.push(i);
        }
      }
    }
  }
  return res;
};
// @lc code=end

复杂度分析

时间复杂度 $O(N*M)$

空间复杂度 $O(M)$