问题
给定一个字符串 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”]
输出：[]
实现代码
package main
import (
"fmt"
"strings"
)
func main() {
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
}
}
var checkPos func(inputStr string, words []string) bool
checkPos = func(inputStr string, words []string) bool {
if len(words) == 0 {
return true
}
for i := 0; i < len(words); i++ {
if strings.HasPrefix(inputStr, words[i]) {
// words里删除index=i 的元素
wordsLeft := make([]string, len(words)-1, len(words)-1)
slotId := 0
for index := 0; index < len(words); index++ {
if index == i {
continue
}
wordsLeft[slotId] = words[index]
slotId++
}
if checkPos(inputStr[len(words[i]):], wordsLeft) {
return true
}
}
}
return false
}
for i := 0; i < len(inputStr); i++ {
iStr, words, tarPos := inputStr[i], vecWords[i], []int{}
nLen := 0
for i := 0; i < len(words); i++ {
nLen = nLen + len(words[i])
}
for startPos := 0; startPos < len(iStr); startPos++ {
startPos = getStartPos(iStr, words, startPos)
if startPos < 0 {
break
}
if checkPos(iStr[startPos:], words) {
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