力扣 30. 串联所有单词的子串
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
方案一：用无序映射保存出现的所有单词的次数，然后遍历字符串，截取长度和 words 字母数量一样的字串进行校验。
func findSubstring(s string, words []string) (ans []int) {
// 每个单词的长度
k := len(words[0])
// 所有单词的长度
tot := len(words) * k
// 统计 words 中出现的单词及其出现次数
mp := make(map[string]int, len(words))
for _, word := range words {
mp[word]++
}
ans = make([]int, 0, len(s) / tot)
// 遍历字符串
for i := 0; i + tot <= len(s); i++ {
// 截取字符串，使其长度可以恰好容纳 words 中的所有单词
if valid(s[i:i+tot], k, mp) {
ans = append(ans, i)
}
}
return
}
// valid 判断字符串 s 是否由 wordsMap 中的单词构成。
func valid(s string, step int, wordsMap map[string]int) bool {
splitWorkdsMap := make(map[string]int)
for i := 0; i + step <= len(s); i += step {
// 截取完整单词
word := string(s[i:i+step])
// 判断单词是否存在于 words 中
if _, ok := wordsMap[word]; !ok {
return ok
}
splitWorkdsMap[word]++
}
// 判断字符串切开后的组成单词种类上是否可 words 中的一致
if len(splitWorkdsMap) != len(wordsMap) {
return false
}
return equalsMap(splitWorkdsMap, wordsMap)
}
// equalsMap 判断两个 map 是否值相等。
func equalsMap(a, b map[string]int) bool {
for k, v := range a {
if b[k] != v {
return false
}
}
for k, v := range b {
if a[k] != v {
return false
}
}
return true
}
- 时间复杂度：O(n)，因为需要遍历所有字母，所以时间复杂度为 O(n)。
- 空间复杂度：O(len(words))，因为使用了长度不超 len(words) 的无序映射，所以空间复杂度为 O(len(words))。