gpt-4o-2024-08-06· OpenAI
WildChat-4.8M (AI2)
Give simple, common, and optimised Java solution class WordDictionary € public…
- User
Give simple, common, and optimised Java solution
class WordDictionary € public WordDictionary) { public void addword(String word) { public boolean search (String word) { /**
- Your WordDictionary object will be instantiated and called as such:
- WordDictionary obj = new WordDictionary:
- obj. addWord (word) :
- boolean param_2 = obj. search (word) ; */
- Assistant
To implement a
WordDictionaryclass that efficiently supportsaddWordandsearch(wheresearchcan handle '.' as a wildcard), using a Trie (prefix tree) is a common and optimized approach. Here's a simple Java solution using a Trie:class WordDictionary { private TrieNode root; public WordDictionary() { root = new TrieNode(); } public void addWord(String word) { TrieNode current = root; for (char c : word.toCharArray()) { if (!current.children.containsKey(c)) { current.children.put(c, new TrieNode()); } current = current.children.get(c); } current.isWord = true; } public boolean search(String word) { return searchRecursive(word, 0, root); } private boolean searchRecursive(String word, int index, TrieNode node) { if (index == word.length()) { return node.isWord; } char c = word.charAt(index); if (c == '.') { for (char key : node.children.keySet()) { if (searchRecursive(word, index + 1, node.children.get(key))) { return true; } } return false; } else { return node.children.containsKey(c) && searchRecursive(word, index + 1, node.children.get(c)); } } private class TrieNode { Map<Character, TrieNode> children; boolean isWord; TrieNode() { children = new HashMap<>(); isWord = false; } } }Explanation:
-
Trie Structure:
TrieNode: This is the basic component of the Trie. Each node contains a mapchildrenthat maps characters to their respective child nodes and a booleanisWordindicating whether a node completes a word.
-
addWord:- Iterate through each character in the word. If the character isn’t already a child of the current node, add it.
- Move to the next node corresponding to the character.
- Mark the final node as the end of a word.
-
search:- Use a recursive helper method
searchRecursiveto handle searching, including checking for the '.' wildcard. - Traverse the Trie according to the characters in the word.
- If a '.' is encountered, recursively attempt to search through all child nodes as they represent all possible characters.
- Use a recursive helper method
This structure allows adding words and searching with possible wildcards efficiently by leveraging the Trie’s prefix storage capability.
-