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

福大大架构师每日一题

发布于 2024-01-18 15:51:14

1550

发布于 2024-01-18 15:51:14

文章被收录于专栏：福大大架构师每日一题

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