2024-01-17：lc 的 30. 串联所有单词的子串

作者：福大大架构师每日一题

2024-01-17
北京
本文字数：2091 字
阅读完需：约 7 分钟

2024-01-17：用 go 语言，给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。

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

例如，如果 words = ["ab","cd","ef"]，

那么 "abcdef"， "abefcd"，"cdabef"，

"cdefab"，"efabcd"，和 "efcdab" 都是串联子串，

"acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。

你可以以任意顺序返回答案。

1 <= s.length <= 10^4，

1 <= words.length <= 5000，

1 <= words[i].length <= 30。

words[i] 和 s 由小写英文字母组成。

输入：s = "barfoothefoobarman", words = ["foo","bar"]。

输出：[0,9]。

来自 lc 的 30. 串联所有单词的子串。

答案 2024-01-17：

来自左程云。

灵捷3.5

大体过程如下：

定义一些常量和变量，包括 BASE 和 MAXN，以及存储结果的切片 ans。
实现 hashValue 函数，用于计算字符串的哈希值。这里使用一个基于索引的简单哈希函数将字符串映射为一个唯一的整数。
实现 buildHash 函数，用于构建字符串的前缀哈希数组。通过动态规划的方式计算每个位置的哈希值。
实现 hashValueRange 函数，用于计算子串的哈希值。利用前缀哈希数组，根据子串的起始和结束位置计算哈希值。
创建一个哈希表 mapCount 用于存储 words 中每个单词的出现次数。
构建字符串 s 的前缀哈希数组 hash。
创建一个数组 pow，用于存储 BASE 的幂次方，便于后续计算子串的哈希值。
创建一个滑动窗口 window，用于记录当前窗口中每个单词出现的次数。
循环遍历 s 中每个起始位置的可能性（即从 0 到 wordLen-1）。
在每个起始位置，初始化一个变量 debt 用于记录还需要凑齐的单词数。
在每个起始位置，遍历 words 中的单词，依次将其添加到窗口中，并更新 debt 的值。
如果 debt 等于 0，表示窗口中已经包含了所有 words 中的单词，则将当前起始位置加入结果数组 ans 中。
对于每个起始位置，向右移动窗口，同时更新窗口中单词的出现次数。
检查窗口中的哈希值和单词出现次数是否符合要求，如果符合则将当前起始位置加入结果数组 ans 中。
清空滑动窗口 window。
返回结果数组 ans。

总的时间复杂度：O(n * m * k)，其中 n 是字符串 s 的长度，m 是 words 的长度，k 是单词的平均长度。

总的额外空间复杂度：O(n)，其中 n 是字符串 s 的长度，主要用于存储哈希表、前缀哈希数组和结果数组。

go 完整代码如下：

package main
import (  "fmt")
var BASE = 499var MAXN = 10001
func hashValue(str string) int64 {  if str == "" {    return 0  }  n := len(str)  ans := int64(str[0]-'a') + 1  for j := 1; j < n; j++ {    ans = ans*int64(BASE) + int64(str[j]-'a') + 1  }  return ans}
func buildHash(str string) []int64 {  hash := make([]int64, len(str))  hash[0] = int64(str[0]-'a') + 1  for j := 1; j < len(str); j++ {    hash[j] = hash[j-1]*int64(BASE) + int64(str[j]-'a') + 1  }  return hash}
func hashValueRange(l, r int, hash []int64, pow []int64) int64 {  ans := hash[r-1]  if l > 0 {    ans -= hash[l-1] * pow[r-l]  }  return ans}
func findSubstring(s string, words []string) []int {  var ans []int  if len(s) == 0 || len(words) == 0 {    return ans  }
  wordLen := len(words[0])  wordNum := len(words)  allLen := wordLen * wordNum
  mapCount := make(map[int64]int)  for _, key := range words {    v := hashValue(key)    mapCount[v]++  }
  hash := buildHash(s)  pow := make([]int64, MAXN)  pow[0] = 1  for j := 1; j < MAXN; j++ {    pow[j] = pow[j-1] * int64(BASE)  }
  window := make(map[int64]int)
  for init := 0; init < wordLen && init+allLen <= len(s); init++ {    debt := wordNum    for l, r, part := init, init+wordLen, 0; part < wordNum; l += wordLen {      cur := hashValueRange(l, r, hash, pow)      window[cur]++      if window[cur] <= mapCount[cur] {        debt--      }      r += wordLen      part++    }    if debt == 0 {      ans = append(ans, init)    }
    for l1, r1, l2, r2 := init, init+wordLen, init+allLen, init+allLen+wordLen; r2 <= len(s); l1, r1, l2, r2 = l1+wordLen, r1+wordLen, l2+wordLen, r2+wordLen {      out := hashValueRange(l1, r1, hash, pow)      in := hashValueRange(l2, r2, hash, pow)      window[out]--      if window[out] < mapCount[out] {        debt++      }      window[in]++      if window[in] <= mapCount[in] {        debt--      }      if debt == 0 {        ans = append(ans, r1)      }    }
    for key := range window {      delete(window, key)    }  }
  return ans}
func main() {  s := "barfoothefoobarman"  words := []string{"foo", "bar"}
  result := findSubstring(s, words)
  fmt.Println(result)}