leetcode-go/hard/30.go

package main

func findSubstring(s string, words []string) []int {
	indices := []int{}
	strLen, wordCnt := len(s), len(words)
	if strLen == 0 || wordCnt == 0 {
		return indices
	}
	dict := make(map[string]int) // May contains duplicate words!
	for _, word := range words {
		dict[word]++
	}
	wordLen := len(words[0])
	for i := 0; i < wordLen; i++ {
		left, count := i, 0
		occur := make(map[string]int)
		for j := i; j <= strLen-wordLen; j += wordLen {
			word := s[j : j+wordLen]
			// If word is valid, accumulate results
			if _, ok := dict[word]; ok {
				occur[word]++
				if occur[word] <= dict[word] {
					count++
				} else {
					// One more word occur, shift the left side of window
					for occur[word] > dict[word] {
						leftWord := s[left : left+wordLen]
						occur[leftWord]--
						if occur[leftWord] < dict[leftWord] {
							count--
						}
						left += wordLen
					}
				}
				// Come to a result
				if count == wordCnt {
					indices = append(indices, left)
					// Advance left side by one word
					occur[s[left:left+wordLen]]--
					count--
					left += wordLen
				}
			} else {
				// Not in word dict, reset all
				occur = make(map[string]int)
				count = 0
				left = j + wordLen
			}
		}
	}
	return indices
}

// func main() {
// 	fmt.Println(findSubstring(
// 		"wordgoodgoodgoodbestword",
// 		[]string{"word", "good", "best", "good"}))
// 	fmt.Println(findSubstring(
// 		"foobarfoobar",
// 		[]string{"foo", "bar"}))
// }