golang 笔试题 串联所有单词的子串

问题

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