Description
tag: Hash Table, Two Pointers, String difficulty: Hard
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.Example:Input: s = "barfoothefoobarman", words = ["foo","bar"]Output: [0,9]Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.The output order does not matter, returning [9,0] is fine too.
Note: 原题第二个例子中每个 word 的长度不一样，在此去掉
Solution
思路：建立一个map，遍历当前字符串， 当所有的 word 都出现过，记录当前位置，继续向后
func findSubstring(s string, words []string) []int { if len(words) == 0{ return []int{} } wordsMap := make(map[string]int, len(words)) for _,value := range words { wordsMap[value] = wordsMap[value] + 1 } var result []int wordLen := len(words[0]) bakWordsMap :=make(map[string]int, len(words)) for i:=0;i 遇到的问题：
- words 为空字符串问题
- words 中可以可以出现相同的单词
Note：
从这个题中才看出 go 的 map 操作很昂贵，看了其他人的提交，基本思路是一致的，但别人的运行时间只有12ms，而我这个是1993ms，修改了两次减少map的使用，运行时间就大幅减少，这是语言的问题，和方法无关，因此只优化了两次。
贴一下最后的优化，运行时间减少一半在900ms左右
func findSubstring(s string, words []string) []int { if len(words) == 0{ return []int{} } wordsMap := make(map[string]int, len(words)) for _,value := range words { wordsMap[value] = wordsMap[value] + 1 } var result []int wordLen := len(words[0]) bakWordsMap :=make(map[string]int) matchCount := len(words) for i:=0;i 0 { bakWordsMap[word]= bakWordsMap[word] + 1 wordsMap[word] = wordsMap[word] - 1 matchCount-- if matchCount == 0 { result = append(result, i) break } } else { break } } matchCount = len(words) for s,i := range bakWordsMap { wordsMap[s] = wordsMap[s] + i } bakWordsMap =make(map[string]int) } return result}