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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | 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); */ |
评论 (0)
