题解
读懂题是第一步, 本题要将句子中所有的单词替换为在词典中对应的它的前缀形式(如果字典中存在这个单词的前缀的话), 最直接的思路就是遍历句子中的所有单词, 将每个单词依次和词典中的所有单词比较, 看词典中是否存在它的前缀, 但这种方法无疑效率极低, 这个场景和我们日常查词典有些相似, 想想我们日常在词典中查一个单词是如何快速定位的, 当然是按照字母顺序在词典中先定位第一个字母的范围, 再定位第二个字母的范围…,最后找到需要的单词. 现在只要把这种方法表示出来就可以大大加快寻找前缀的速度. 这样就可以构造一棵词典树, 树的边表示不同的字母, 节点可以用来标定是否是一个可行单词. 再去查找某个单词的前缀的时候, 只需要去树中执行bfs找到最短的可行前缀即可.
代码
type TreeNodes struct{
node [26]*TreeNodes
over bool
}
func construct(dic []string) *TreeNodes{
root := TreeNodes{}
var point *TreeNodes
for _, str := range dic{
point = &root
for i,_ := range str{
if point.node[str[i]-'a']==nil{
newnode := &TreeNodes{}
point.node[str[i]-'a'] = newnode
point = newnode
}else{
point = point.node[str[i]-'a']
}
}
point.over = true
}
return &root
}
func findWord(root *TreeNodes, word string)(bool, string){
var point *TreeNodes
point = root
prefix := []byte{}
for i,_ := range word{
if point.node[word[i]-'a'] == nil{
return false,""
}else{
prefix = append(prefix, word[i])
point = point.node[word[i]-'a']
if point.over{
return true, string(prefix)
}
}
}
return false,""
}
func replaceWords(dictionary []string, sentence string) string {
root := construct(dictionary)
sentenceArray := strings.Split(sentence, " ")
exist, str := false, ""
for i, word := range sentenceArray{
exist, str = findWord(root, word)
if exist{
sentenceArray[i] = str
}else{
sentenceArray[i] = word
}
}
return strings.Join(sentenceArray, " ")
}
总结
注意直接使用"+“在go中进行字符串连接是非常耗时的, 因此可以将原句子分割后得到字符串数组, 查询是否存在单词的可行前缀并直接替换对应数组中的字符串, 最后再调用strings.Join将数组中的所有字符串使用空格连接, 可以自行测试如果对数组中每个字符串在查找其可行前缀后都使用”+"连接到结果字符串上耗时远远大于这种方案.