2024-01-17:lc的30. 串联所有单词的子串
2024/1/18 5:02:31
本文主要是介绍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
大体过程如下:
-
定义一些常量和变量,包括
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 = 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) }
这篇关于2024-01-17:lc的30. 串联所有单词的子串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升