滑动窗口:golang实现串联所有单词的子串算法

欢迎大家来到IT世界,在知识的湖畔探索吧!

题目介绍:给定一个字符串 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] 也是可以的。 

欢迎大家来到IT世界,在知识的湖畔探索吧!

示例 2：

欢迎大家来到IT世界,在知识的湖畔探索吧!输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[] 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。

实现逻辑：双指针 + hashmap + word计数

完整代码如下：

package main import ( "fmt" "testing" ) func findSubstring(s string, words []string) []int { if len(words) == 0 { return nil } wordLen := len(words[0]) totalLen := wordLen * len(words) if totalLen > len(s) { return nil } wordCount := make(map[string]int) for _, word := range words { wordCount[word]++ } var result []int for i := 0; i <= len(s)-totalLen; i++ { tempCount := make(map[string]int) j := 0 for j < len(words) { word := s[i+j*wordLen : i+(j+1)*wordLen] if count, ok := wordCount[word]; ok { tempCount[word]++ if tempCount[word] > count { break } } else { break } j++ } if j == len(words) { result = append(result, i) } } return result } func TestSubIndex(t *testing.T) { s := "barfoothefoobarman" words := []string{"foo", "bar"} result := findSubstring(s, words) fmt.Println(result) // Output: [0 9] }