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())
}