211. Design Add and Search Words Data Structure

Published on March 30, 2023

Problem

Design a data structure that supports addWord and searchWord. and in search, there may be fuzzy searches, i.e. . represents any character. The maximum number of occurrences is two.

Algorithm

This problem sees add and searchword, we can consider using trie to achieve a better search time complexity.

It is somewhat similar to implementation trie, but here the search method appears to be a fuzzy match. So it needs to be handled separately for dot notation. This topic is not like the tenth question regular matching that assistance, involving some association before and after, but simply a point represents a character. Then we do not know what he represents, we need to search for each possible child node, as long as he has a child node to meet the matching conditions, you can return true.

For ordinary characters, we can compare and match characters to see if there is a corresponding child node.

A recursive method is used here to achieve this.

Code

class WordDictionary {
    TrieNode root.

    public WordDictionary() {
        root = new TrieNode().
    }
    
    public void addWord(String word) {
        TrieNode curNode = root.
        for (Character c : word.toCharArray()) {
            if (curNode.children[c-'a'] == null) {
                curNode.children[c-'a'] = new TrieNode().
            }
            curNode = curNode.children[c-'a'].
        }
        curNode.isWord = true.
    }
    
    public boolean search(String word) {
        return search(word, 0, root).
    }
    
    private boolean search(String word, int index, TrieNode curNode) {
        if (index == word.length()) {
            return curNode.isWord.
        }
        Character c = word.charAt(index).
        if (c == '.') {
            for (TrieNode child : curNode.children) {
                if (child ! = null && search(word, index+1, child)) {
                    return true.   
                }
            }
        } else {
            TrieNode child = curNode.children[c-'a'].
            return child ! = null && search(word, index+1, child).
        }
        return false.
    }
    
    class TrieNode {
        boolean isWord.
        TrieNode[] children.
        public TrieNode() {
            isWord = false.
            children = new TrieNode[26].
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such.
 * WordDictionary obj = new WordDictionary().
 * obj.addWord(word).
 * boolean param_2 = obj.search(word).
 */

问题

设计一个数据结构，支持addWord和searchWord。而且在search中，可能出现模糊搜索，即.代表任意字符。最多出现两次。

算法

这个问题看到add和searchword，我们可以考虑使用trie达到更好的搜索时间复杂度。

和implement trie有些类似，不过这里search方法出现了模糊匹配。所以需要对于点符号单独处理。这个题目不像第十题正则匹配那个辅助，涉及到前后的一些关联，只是单纯一个点代表一个字符。那我们不知道他代表什么，需要对于每一个可能存在的孩子节点去进行搜索，只要他有孩子节点满足匹配条件，就可以返回true。

对于普通的字符，进行字符比较匹配看是否有对应的孩子节点即可。

这里使用了一个递归的方法来实现。

代码

class WordDictionary {
    TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode curNode = root;
        for (Character c : word.toCharArray()) {
            if (curNode.children[c-'a'] == null) {
                curNode.children[c-'a'] = new TrieNode();
            }
            curNode = curNode.children[c-'a'];
        }
        curNode.isWord = true;
    }
    
    public boolean search(String word) {
        return search(word, 0, root);
    }
    
    private boolean search(String word, int index, TrieNode curNode) {
        if (index == word.length()) {
            return curNode.isWord;
        }
        Character c = word.charAt(index);
        if (c == '.') {
            for (TrieNode child : curNode.children) {
                if (child != null && search(word, index+1, child)) {
                    return true;   
                }
            }
        } else {
            TrieNode child = curNode.children[c-'a'];
            return child != null && search(word, index+1, child);
        }
        return false;
    }
    
    class TrieNode {
        boolean isWord;
        TrieNode[] children;
        public TrieNode() {
            isWord = false;
            children = new TrieNode[26];
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */