April 14, 2020
https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
func findSubstring(s string, words []string) []int {
var result []int
if len(s) == 0 || len(words) == 0 {
return result
}
wordMap := generateWordMap(words)
start := -1
stepSize := len(words[0])
i := 0
wordCount := 0
for i < len(s) {
if i+stepSize > len(s) {
if start > -1 {
i = start + 1
start = -1
wordMap = generateWordMap(words)
wordCount = 0
continue
} else {
break
}
}
subStr := string(s[i:i+stepSize])
if wordMap[subStr] > 0 {
wordMap[subStr]--
wordCount++
if start == -1 {
start = i
}
i += stepSize
} else if start == -1 {
i++
} else {
i = start + 1
wordMap = generateWordMap(words)
start = -1
wordCount = 0
}
if wordCount == len(words) {
result = append(result, start)
i = start + 1
wordMap = generateWordMap(words)
start = -1
wordCount = 0
}
}
return result
}
func generateWordMap(words []string) (wordMap map[string]int) {
wordMap = make(map[string]int)
for _, word := range words {
wordMap[word] = wordMap[word] + 1
}
return wordMap
}
题目其实并不难,就是实现上会比较绕,只要有一个清晰的思路,写下去就不会有问题。这里我说下我的思路,很简单,就是遍历字符串 s,对 s 按照样本字符串的长度进行切片,并从样本字符串中确认该子串是否存在,存在就继续向后找,不存在则重新找到头重新划切片。
因为要找到样本字符串中是否有子串,所以我先构造了一个 map 结构,而样本字符串可能存在同一个字符串出现多次的情况,所以 map 的值我用字符串出现的次数来填充。在遍历的过程中,访问到过一次,就减一,以确保数量能对上。而一旦本轮匹配失败,就需要重置这个匹配计数器。
这里先想好什么是一轮成功的匹配:从某个开始位置进行切片,从这个位置开始连续 n 次匹配到 wordMap 中的字符串,并且最终 n == len(words),则此为一轮成功的匹配,此开始位置也是一个成功解。那么很自然,不成功的匹配首先一定是子串在 wordMap 中没找到。而在不成功的场景中,也需要分是开始就不成功还是匹配了一部分之后的不成功。这里涉及到对 i 的处理。不成功的场景也要对各种计量值进行重置,以免影响下次匹配。
痕迹
没有过去,就没法认定现在的自己