leetcode_820

Golang:

思路：最开始的思路接近于枚举法，后来逆向思考了一下，觉得是字典树结构，但是这个实现的效率很低

代码如下：

type Words []string
func (s Words) Len() int           { return len(s) }
func (s Words) Less(i, j int) bool { return len(s[i]) > len(s[j]) }
func (s Words) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func minimumLengthEncoding(words []string) int {
    res:=0
    sort.Sort(Words(words))
    tree:=Trie{}
    for _,v:=range words{
        tmp:=reBuildstr(v)
        if !tree.StartsWith(tmp) {
            tree.Insert(tmp)
            res += len(v)+1
        }
    }
    return res
}

func reBuildstr(word string)string{
    var res strings.Builder
    for i:=len(word)-1;i>=0;i--{
        res.WriteByte(word[i])
    }
    return res.String()
}

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 there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    temp := this
    for _, v := range prefix {
        nxt := v - 'a'
        if temp.next[nxt] == nil {
            return false
        } else {
            temp = temp.next[nxt]
        }
    }
    return true
}

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