分享
leetcode_820
淳属虚构 · · 1064 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
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
}
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1064 次点击
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
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
}