Leetcode - Replace Words

https://leetcode.com/problems/replace-words/

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Yet another Trie.

func replaceWords(dict []string, sentence string) string {
    root := buildTrie(dict)
    words := strings.Split(sentence, " ")
    //fmt.Println("try: ", search(root, "ba"))
    for i := 0; i < len(words); i++ {
        searched := search(root, words[i])
        if searched != "" {
            words[i] = searched
        }
    }
    return strings.Join(words, " ")
}

type Trie struct {
    Val string
    Leaf bool
    Children []*Trie
}

func buildTrie(dict []string) *Trie {
    root := &Trie{
        Children: make([]*Trie, 26),
    }
    for _, d := range dict {
        node := root
        for i := 0; i < len(d); i++ {
            index := d[i] - 'a'
            if node.Children[index] == nil {
                node.Children[index] = &Trie{
                    Children: make([]*Trie, 26),
                }
            }
            node = node.Children[index]
        }
        node.Val = d
        node.Leaf = true
    }
    return root
}


func search(root *Trie, word string) string{
    node := root
    for i := 0; i < len(word); i++ {
        if node.Leaf {
            return node.Val
        }
        index := word[i] - 'a'
        //fmt.Println("index: ", index)
        
        if node.Children[index] != nil {
           node = node.Children[index]
        } else {
            return node.Val
        }
    }
    return node.Val
}

• 相关文章
• 全局相关文章