leetcode_820

淳属虚构 · · 152 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:淳属虚构

查看原文:leetcode_820

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

152 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传