Design Add and Search Words
MediumThe problem
Build a WordDictionary. AddWord(word) stores a word. Search(word) returns true if some stored word matches it, where each "." in the search can stand for any single letter.
- Example 1Input: AddWord("bad") AddWord("dad") AddWord("mad") Search("pad") Search("bad") Search(".ad") Search("b..")Output: false, true, true, true
No stored word is "pad". "bad" is stored. ".ad" matches bad, dad or mad. "b.." matches "bad". (AddWord returns nothing.)
- 1 ≤ word.length ≤ 25
- Added words only have lowercase letters; searches may also contain "."
- At most 2 dots in any search
- Up to 10,000 calls in total
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Only the "." character is special: it can be any letter, so you must try all children.
The idea
Trie plus recursive search; on "." recurse into every child and return true if any succeeds.
Target: O(len) add, O(26^dots · len) worst-case search
Go function shape
type WordDictionary struct{}
func Constructor() WordDictionary
func (w *WordDictionary) AddWord(word string)
func (w *WordDictionary) Search(word string) boolReference solution
Tested with go test. Try it yourself first, then compare.
// WordDictionary: Search treats '.' as "any single letter".
type WordDictionary struct{ t *Trie }
func NewWordDictionary() *WordDictionary { return &WordDictionary{t: NewTrie()} }
func (w *WordDictionary) AddWord(word string) { w.t.Insert(word) }
func (w *WordDictionary) Search(word string) bool {
var match func(n *node, rest []rune) bool
match = func(n *node, rest []rune) bool {
if len(rest) == 0 {
return n.end
}
if rest[0] == '.' { // wildcard: try every child
for _, child := range n.next {
if match(child, rest[1:]) {
return true
}
}
return false
}
child := n.next[rest[0]]
return child != nil && match(child, rest[1:])
}
return match(w.t.root, []rune(word))
}