648. Replace Words
给一组string array dictionary以sentance
sentance是由多个单字跟空格所组成
请将sentance里的单字用dictionary里的root代替
若有多个root，请用最短的那个
root就是该单字的前缀字
思路:
有两种(1)用字典树(2)用hash table
(1)字典树
这个就很直观，用一个字典树纪录所有dictionary的单字
接着将sentance分成多个单字，一个一个去找最短的root
(2)hash table
先将dictionary的单字依照长度排序
再用一个hash table依照字首字母去记录每个单字
接着一样将sentance分成多个单字，一个一个去找最短的root
golang code
(1)字典树
type node struct {
end int16
char [26]*node
}
func replaceWords(dictionary []string, sentence string) string {
tire := &node{-1, [26]*node{}}
res := strings.Builder{}
for key, val := range dictionary {
head, n := tire, len(val)
for i := 0; i < n; i++ {
if head.char[val[i]-'a'] == nil {
head.char[val[i]-'a'] = &node{-1, [26]*node{}}
}
head = head.char[val[i]-'a']
}
head.end = int16(key + 1)
}
words := strings.Split(sentence, " ")
for _, val := range words {
n, found, head := len(val), false, tire
for i := 0; i < n; i++ {
if head.char[val[i]-'a'] != nil {
head = head.char[val[i]-'a']
if head.end > 0 {
res.WriteString(dictionary[head.end-1])
found = true
break
}
}else{
break
}
}
if !found {
res.WriteString(val)
}
res.WriteString(" ")
}
(2)hash table
func replaceWords(dictionary []string, sentence string) string {
var res strings.Builder
slices.SortFunc(dictionary, func(i, j string) int {
return len(i) - len(j)
})
rec := make([][]string, 26)
for _, val := range dictionary {
rec[val[0]-'a'] = append(rec[val[0]-'a'], val)
}
words := strings.Split(sentence, " ")
n := len(words)
for i := 0; i < n; i++ {
found := false
for _, val := range rec[words[i][0]-'a'] {
if strings.HasPrefix(words[i], val) {
res.WriteString(val)
found = true
break
}
}
if !found {
res.WriteString(words[i])
}
res.WriteString(" ")
}
return strings.TrimSpace(res.String())
}