You are given a string, s, and a list of words, words, that are all of the same length.
Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).
func findSubstring(s string, words []string) []int {
var ret[]int=make([]int,0)
if len(words)==0 {
return ret
}
size:=len(words)*len(words[0])
var tmp string
for i:=0;i<len(s);i++{
if i+size>len(s){
break
}
tmp=s[i:i+size]
if compare(tmp,words){
ret=append(ret, i)
}
}
return ret
}
func compare(s string, words []string)bool{
step:=len(words[0])
var sig[]bool=make([]bool,len(words))
for i:=0;i<len(words);i++{
sig[i]=false
}
for i:=0;i<len(s);i+=step{
tmp:=s[i:i+step]
j:=0
for ;j<len(sig);j++{
if !sig[j]&&tmp==words[j]{
sig[j]=true
break
}
}
if j==len(sig){
return false
}
}
return true
}
性能不达标
func findSubstring(s string, words []string) []int {
var ret[]int
var comps[]string=strs(words)
for i:=0;i<len(s)-len(comps[0])+1;i++{
for j:=0;j<len(comps);j++{
if comps[j]==s[i:i+len(comps[j])]{
ret=append(ret, i)
break
}
}
}
return ret
}
func strs(words []string)[]string{
var ret[]string=make([]string,0)
for i:=0;i<len(words);i++{
var tmp[]string=strs(pop(words,i))
if len(tmp)==0{
ret=append(ret, words[i])
}
for j:=0;j<len(tmp);j++{
if !contain(ret,words[i]+tmp[j]){
ret=append(ret,words[i]+tmp[j])
}
if !contain(ret,tmp[j]+words[i]){
ret=append(ret,tmp[j]+words[i])
}
}
}
return ret
}
func contain(words []string,str string)bool{
for i:=0;i<len(words);i++{
if words[i]==str{
return true
}
}
return false
}
func pop(words []string,index int) []string {
var ret[]string=make([]string,0)
for i:=0;i<len(words);i++{
if i!=index{
ret=append(ret, words[i])
}
}
return ret
}