问题
给定一个字符串 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