Problem
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary
class:
WordDictionary()
Initializes the object.void addWord(word)
Addsword
to the data structure, it can be matched later.bool search(word)
Returnstrue
if there is any string in the data structure that matchesword
orfalse
otherwise.word
may contain dots'.'
where dots can be matched with any letter.
Example:
Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True
Solution
此題要我們建立一個 word dictionary,這很明顯就是要使用 Trie。不過題目還要求支援 dots '.'
。在搜尋的時候,它可以匹配任何字元。因此,當遇到 '.'
的時候,我們必須要搜尋該 node 的所有 children,直到找到匹配的字串。
Trie
class WordDictionary { class TrieNode { private Map<Character, TrieNode> children = new HashMap<>(); private char character; private boolean terminates = false; TrieNode() { } TrieNode(char character) { this.character = character; } void addWord(String word) { if (word == null || word.isEmpty()) return; char firstChar = word.charAt(0); TrieNode child = children.get(firstChar); if (child == null) { child = new TrieNode(firstChar); children.put(firstChar, child); } if (word.length() > 1) { child.addWord(word.substring(1)); } else { child.setTerminates(true); } } boolean search(String word) { if (word == null || word.isEmpty()) return false; char firstChar = word.charAt(0); if (firstChar == '.') { String subWord = word.substring(1); if (subWord.isEmpty()) { for (TrieNode child : children.values()) { if (child.terminates) { return true; } } } else { for (TrieNode child : children.values()) { if (child.search(subWord)) { return true; } } } } else { if (children.containsKey(firstChar)) { TrieNode child = children.get(firstChar); if (word.length() == 1) { return child.terminates; } else { return child.search(word.substring(1)); } } } return false; } void setTerminates(boolean terminates) { this.terminates = terminates; } } private TrieNode root = new TrieNode(); public WordDictionary() { } public void addWord(String word) { root.addWord(word); } public boolean search(String word) { return root.search(word); } }
參考
- 211. Design Add and Search Words Data Structure, LeetCode.
- 211. Design Add and Search Words Data Structure, LeetCode Solutions.