golang 笔试题 串联所有单词的子串(map比较)

问题

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：
s = “barfoothefoobarman”,
words = [“foo”,”bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,”good”,”best”,”word”]
输出：[]

代码

// 使用计数的方式实现
func Test6() {
	inputStr := []string{"barfoothefoobarman", "wordgoodgoodgoodbestword", "wordgoodgoodwordgoodbestword"}
	vecWords := [][]string{{"foo", "bar"}, {"word", "good", "best", "word"}, {"word", "good", "best", "word"}}

	getStartPos := func(inputStr string, words []string, startPos int) int {
		dstPos := -1
		for i := 0; i < len(words); i++ {
			if index := strings.Index(inputStr[startPos:], words[i]); index != -1 {
				if dstPos == -1 {
					dstPos = index
				} else {
					if dstPos > index {
						dstPos = index
					}
				}
			}
		}
		if dstPos == -1 {
			return -1
		} else {
			return dstPos + startPos
		}
	}

	makeTarget := func(inputStr string, startPos, wordLen, wordCount int) map[string]int {
		ret := make(map[string]int)
		wc := 0
		for startPos < len(inputStr) && startPos+wordLen <= len(inputStr) && wc < wordCount {
			if value, ok := ret[inputStr[startPos:startPos+wordLen]]; ok {
				ret[inputStr[startPos:startPos+wordLen]] = value + 1
			} else {
				ret[inputStr[startPos:startPos+wordLen]] = 1
			}
			startPos = startPos + wordLen
			wc++
		}
		return ret
	}
	makeBase := func(words []string) map[string]int {
		ret := make(map[string]int)
		for i := 0; i < len(words); i++ {
			if value, ok := ret[words[i]]; ok {
				ret[words[i]] = value + 1
			} else {
				ret[words[i]] = 1
			}
		}
		return ret
	}

	isMapEqual := func(a, b map[string]int) bool {
		ret := reflect.DeepEqual(a, b)
		if ret {
			fmt.Printf("%v == %v\n", a, b)
		} else {
			fmt.Printf("%v != %v\n", a, b)
		}

		return ret
	}

	for i := 0; i < len(inputStr); i++ {
		iStr, words, tarPos := inputStr[i], vecWords[i], []int{}
		nLen, wordLen := 0, len(words[0])
		for i := 0; i < len(words); i++ {
			nLen = nLen + len(words[i])
		}
		base := makeBase(words)

		for startPos := 0; startPos < len(iStr); startPos++ {
			startPos = getStartPos(iStr, words, startPos)
			if startPos < 0 {
				break
			}
			target := makeTarget(iStr, startPos, wordLen, len(words))
			if isMapEqual(base, target) {
				tarPos = append(tarPos, startPos)
			}
		}
		if len(tarPos) > 0 {
			fmt.Printf("input str=%s, words=%v\n", iStr, words)
			for i := 0; i < len(tarPos); i++ {
				fmt.Printf("find target postition=%d, target string=%s \n", tarPos[i], iStr[tarPos[i]:tarPos[i]+nLen])
			}
			fmt.Printf("\n")
		} else {
			fmt.Printf("input str=%s, words=%v find nothing.\n\n", iStr, words)
		}
	}
}

执行结果

input str=barfoothefoobarman, words=[foo bar]
find target postition=0, target string=barfoo
find target postition=9, target string=foobar

input str=wordgoodgoodgoodbestword, words=[word good best word] find nothing.

input str=wordgoodgoodwordgoodbestword, words=[word good best word]
find target postition=12, target string=wordgoodbestword