Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-08-06· OpenAIAi2 WildChat-4.8M (AI2)

Give simple, common, and optimised Java solution class WordDictionary € public…

  1. 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) ; */
  2. Assistant

    To implement a WordDictionary class that efficiently supports addWord and search (where search can 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 map children that maps characters to their respective child nodes and a boolean isWord indicating 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 searchRecursive to 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.

    This structure allows adding words and searching with possible wildcards efficiently by leveraging the Trie’s prefix storage capability.