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

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

大体过程如下：

1. 定义一些常量和变量，包括BASE和MAXN，以及存储结果的切片ans。

2. 实现hashValue函数，用于计算字符串的哈希值。这里使用一个基于索引的简单哈希函数将字符串映射为一个唯一的整数。

3. 实现buildHash函数，用于构建字符串的前缀哈希数组。通过动态规划的方式计算每个位置的哈希值。

4. 实现hashValueRange函数，用于计算子串的哈希值。利用前缀哈希数组，根据子串的起始和结束位置计算哈希值。

5. 创建一个哈希表mapCount用于存储words中每个单词的出现次数。

6. 构建字符串s的前缀哈希数组hash。

7. 创建一个数组pow，用于存储 BASE 的幂次方，便于后续计算子串的哈希值。

8. 创建一个滑动窗口window，用于记录当前窗口中每个单词出现的次数。

9. 循环遍历s中每个起始位置的可能性（即从 0 到wordLen-1）。

10. 在每个起始位置，初始化一个变量debt用于记录还需要凑齐的单词数。

11. 在每个起始位置，遍历words中的单词，依次将其添加到窗口中，并更新debt的值。

12. 如果debt等于 0，表示窗口中已经包含了所有words中的单词，则将当前起始位置加入结果数组ans中。

13. 对于每个起始位置，向右移动窗口，同时更新窗口中单词的出现次数。

14. 检查窗口中的哈希值和单词出现次数是否符合要求，如果符合则将当前起始位置加入结果数组ans中。

15. 清空滑动窗口window。

16. 返回结果数组ans。

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

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

go完整代码如下：

package main

import (

"fmt"

)

var BASE = 499

var 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)

}

在这里插入图片描述