Leetcode - Implement Magic Dictionary

https://leetcode.com/problems/implement-magic-dictionary/

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

type MagicDictionary struct {
    trie *Node
}

type Node struct {
    val string
    children []*Node
    leaf bool
}


/** Initialize your data structure here. */
func Constructor() MagicDictionary {
    return MagicDictionary{
        trie: &Node{
            children: make([]*Node, 26),
        },
    }
}


/** Build a dictionary through a list of words */
func (this *MagicDictionary) BuildDict(dict []string)  {
    for _, d := range dict {
        node := this.trie
        for i := 0; i < len(d); i++ {
            index := d[i] - 'a'
            if node.children[index] == nil {
                node.children[index] = &Node{
                    children: make([]*Node, 26),
                }
            }
            node = node.children[index]
        }
        node.val = d
        node.leaf = true
    }
}

func trasversal(root *Node) {
    if root == nil {
        return
    }
    for i, c := range root.children {
        if c != nil {
            char := i + 'a'
            fmt.Println(string(char))
            trasversal(c)
        }
        
    }
}

/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
func (this *MagicDictionary) Search(word string) bool {
    return search(word, 0, this.trie, false)
}

func search(word string, i int, node *Node, updated bool) bool {
    if i >= len(word) {
        return updated && node.val != ""
    }
    index := word[i] - 'a'
    if node.children[index] != nil {
        if search(word, i+1, node.children[index], updated) {
            return true
        }
    }
    if !updated {
        for j, c := range node.children {
            if c != nil && byte(j + 'a') != word[i] && search(word, i+1, c, true) {
                return true
            }
        }
    }
    return false
}
/**
 * Your MagicDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.BuildDict(dict);
 * param_2 := obj.Search(word);
 */

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