leetcode_30

Golang:

思路：这题应该用map做会简单一些，但效率不会特别理想，这里补充个前缀树做法，当然，我使用前缀树其实是希望把它写成AC自动机的，这个留到下次吧。

代码如下：

type Trie struct {
    ending bool
    next [26]*Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
    return Trie{}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
    temp:=this
    for _,v:=range word {
        nxt:=v-'a'
        if temp.next[nxt]==nil {
            temp.next[nxt]=&Trie{}
        }
        temp=temp.next[nxt]
    }
    temp.ending=true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    temp:=this
    for _,v:=range word{
        nxt:=v-'a'
        if temp.next[nxt]==nil {
            return false
        }else {
            temp=temp.next[nxt]
        }
    }
    return temp.ending
}
func findSubstring(s string, words []string) []int {
    var res []int
    if len(words)==0{
        return res
    }
    length:=len(words[0])
    mp:=make(map[string]int)
    for i:=0;i<len(words);i++{
        mp[words[i]]++
    }
    trie:=Trie{}
    for k,_:=range mp{
        trie.Insert(k)
    }
    for i:=0;i<=len(s)-length*len(words);i++{
        if trie.Search(s[i:i+length]){
            mp2:=make(map[string]int)
            mp2[s[i:i+length]]++
            flag:=0
            for j:=i+length;j<i+len(words)*length;j+=length{
                if trie.Search(s[j:j+length]) {
                    mp2[s[j:j+length]]++
                    if mp2[s[j:j+length]]>mp[s[j:j+length]]{
                        flag=1
                        break
                    }
                }else{
                    flag=1
                    break
                }
            }
            if flag==0 {
                res=append(res,i)
            }
        }
    }
    return res
}

有疑问加站长微信联系（非本文作者）