【基础篇 - Day 23】 2023-03-07 - 30. 串联所有单词的子串 （04. 哈希表）

[threedayAAAAA]

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

 

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。 示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[] 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。 示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。  

提示：

1 <= s.length <= 104 1 <= words.length <= 5000 1 <= words[i].length <= 30 words[i] 和 s 由小写英文字母组成

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

[threedayAAAAA]

思路

使用滑动窗口，每次滑动一个单词，同时通过hash计算当前窗口内的单词数量是否符合要求。 滑动窗口因为有可能会导致单词被截断，所以遍历k次滑动窗口，k为单词长度

代码

function findSubstring(s: string, words: string[]): number[] {
    const orginWordMap: Record<string, number> = {}
    for(const word of words){
        orginWordMap[word] = orginWordMap[word] ? orginWordMap[word] + 1 : 1
    }
    const getNextWord = (startIndex: number) => s.substr(startIndex, wordLen)
    function initSlide(startIndex: number, wordMap: Record<string, number>){
        for(let i = startIndex; i < startIndex + subStrLen; i += wordLen){
            const word = getNextWord(i)
            if(wordMap[word] !== undefined) wordMap[word] -= 1
        }
    }
    const result = []
    const wordLen = words[0].length
    const subStrLen = wordLen * words.length
    const sLen = s.length
    for(let i = 0; i < wordLen; i++){
        let chaos = words.length
        let cacheMap = {...orginWordMap}
        for(let j = i; j + subStrLen <= sLen; j += wordLen){
            if(j === i) {
                initSlide(i, cacheMap)
                chaos = Object.values(cacheMap).reduce((pre, cur) => pre + Math.abs(cur), 0)
            } else {
                const preWord = getNextWord(j - wordLen)
                const curWord = getNextWord(j + subStrLen - wordLen)
                if(cacheMap[preWord] !== undefined) {
                    chaos += cacheMap[preWord] < 0 ? -1 : 1
                    cacheMap[preWord] += 1
                } 
                if(cacheMap[curWord] !== undefined) {
                    chaos += cacheMap[curWord] > 0 ? -1 : 1
                    cacheMap[curWord] -= 1
                }
            }
            if(chaos === 0) result.push(j)
        }
    }
    return result
};

时空复杂度

• 时间复杂度： wordLen ( [Len(s) - (wordNums wordLen)] / wordLen) ===> O(N)
• 空间复杂度：O(N)

[yunliuyan]

思路

• 滑动窗口，哈希表 + 指针。指针初始化为0，然后跳跃值为jump = words[0].length。从指针所指的s的字符开始截取到 jump * words.length
• 设置一个哈希表hashMap: Map<string, number>,，用来记录words中的元素在截取的字符串出现的次数，若都出现了，则将指针值存到返回接口中
• 没有则跳跃到下一个指针位置，直到指针大于s.length - jump * words.length

代码

function findSubstring(s: string, words: string[]): number[] {
   if (!s || !words.length) { 
    return [];
  }
  const res: number[] = [];
  const hashMap: Map<string, number> = new Map();
  const jump = words[0].length;
  const connectStrLen = jump  * words.length;
  // 初始化哈希表
  const initHashMap = () => {
    hashMap.clear();
    words.forEach(item => hashMap.set(item, (hashMap.get(item) ?? 0) + 1));
  }
  const checkIsConnectChildStr = (point: number) => {
    let isConnectChildStr = true;
    hashMap.forEach(item => {
      if (item !== 0) {
        isConnectChildStr = false;
      }
    })
    isConnectChildStr && res.push(point);
  }

  for(let i = 0; i <= s.length - connectStrLen; i++) {
    initHashMap();
    const curStr = s.substring(i, i + connectStrLen);
    for(let j = 0; j < curStr.length; j += jump) {
      const curChildStr = curStr.substring(j, j + jump);
      if (hashMap.has(curChildStr)) {
        hashMap.set(curChildStr, (hashMap.get(curChildStr) ?? 0) - 1);
      }
    }
    checkIsConnectChildStr(i);
  }
  return res;
};

复杂度分析

• 时间复杂度: O(n*words.length)
• 空间复杂度: O(n)

[MiumMi]

思路

1. 滑动窗口+哈希表，记录words的hash表，（每个字符串出现次数）
2. 每次滑动截取对应words.length * wordLen长度的字符串，记录这个字符串中得hash表（每wordLen长度的字符串出现次数）

3. 如果两个hash一样，则表示这个字符串是符合要求的

   代码

   
   function isSame (hash1, hash2) {
   const keys1 = Object.keys(hash1);
   const keys2 = Object.keys(hash2);
   return keys1.length === keys2.length && keys1.every(key => hash1[key] === hash2[key]);
   }

function findSubstring(s: string, words: string[]): number[] { if (!words.length) { return []; } const wordLen = words[0].length const resultLen = words.length * wordLen; if (s.length < resultLen) { return []; } // 每个字符串出现过几次，则在字符串遍历中只能使用几次 const hash = {}; words.forEach(item => { hash[item] = hash[item] ? hash[item] + 1 : 1; }); let startIndex = 0; let result = []; while(startIndex <= s.length - resultLen) { const endIndex = startIndex + resultLen; if (endIndex > s.length) { break; } const str = s.slice(startIndex, endIndex); const tempHash = {}; for (let i = 0; i < str.length; i += wordLen) { const currentStr = str.slice(i, i + wordLen); if (!hash[currentStr]) { break; } tempHash[currentStr]= tempHash[currentStr] ? tempHash[currentStr] + 1 : 1; } if (isSame(hash, tempHash)) { result.push(startIndex); } startIndex++; } return result; };

---
### 分析
时间复杂度: O(k*n), k为s的长度， n为words的长度 
空间复杂度: O(n);n为words的长度