[LeetCode] Add and Search Word - Data structure design

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Solution: This is based on the post for [LeetCode] Implement Trie (Prefix Tree).

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 84 85 86 87 88 89 90

public class WordDictionary { Trie trie = new Trie(); // Adds a word into the data structure. public void addWord(String word) { trie.insert(word); } // Returns if the word is in the data structure. A word could // contain the dot character '.' to represent any one letter. public boolean search(String word) { return trie.search(word); } } // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern"); class TrieNode { char ch; boolean isWord = false; TrieNode[] children = null; public TrieNode() { } public TrieNode(char c) { this.ch = c; } } class Trie { TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { if (word == null || word.length() == 0) { return; } TrieNode node = root; for (int i = 0; i < word.length(); i++) { if (node.children == null) { node.children = new TrieNode[26]; } int idx = word.charAt(i) - 'a'; if (node.children[idx] == null) { node.children[idx] = new TrieNode(word.charAt(i)); } node = node.children[idx]; if (i == word.length() - 1) { node.isWord = true; } } } public boolean search(String word) { if (word == null || word.length() == 0) { return false; } return DFS(word, 0, root); } public boolean DFS(String word, int i, TrieNode node) { if (node == null) { return false; } if (i == word.length()) { return node.isWord; } if (node.children == null) { return false; } if (word.charAt(i) != '.') { int idx = word.charAt(i) - 'a'; return DFS(word, i + 1, node.children[idx]); } for (int j = 0; j < 26; j++) { if (DFS(word, i + 1, node.children[j])) { return true; } } return false; } }