力扣

作者: 西二旗老司机 | 来源:发表于2019-04-23 14:45 被阅读0次

    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.

    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.

    public class WordDictionary {
        WordNode root = new WordNode();
        public void addWord(String word) {
            char chars[] = word.toCharArray();
            addWord(chars, 0, root);
        }
        
        private void addWord(char[] chars, int index, WordNode parent) {
            char c = chars[index];
            int idx = c-'a';
            WordNode node = parent.children[idx];
            if (node == null){
                node = new WordNode();
                parent.children[idx]=node;
            }
            if (chars.length == index+1){
                node.isLeaf=true;
                return;
            }
            addWord(chars, ++index, node);
        }
    
    
        public boolean search(String word) {
            return search(word.toCharArray(), 0, root);                  
        }
        
        private boolean search(char[] chars, int index, WordNode parent){
            if (index == chars.length){
                if (parent.isLeaf){
                    return true;
                }
                return false;
            }
            WordNode[] childNodes = parent.children;
            char c = chars[index];
            if (c == '.'){
                for (int i=0;i<childNodes.length;i++){
                    WordNode n = childNodes[i];
                    if (n !=null){
                        boolean b = search(chars, index+1, n);
                        if (b){
                            return true;
                        }
                    }
                }
                return false;
            }
            WordNode node = childNodes[c-'a'];
            if (node == null){
                return false;
            }
            return search(chars, ++index, node);
        }
        
    
        
        private class WordNode{
            boolean isLeaf;
            WordNode[] children = new WordNode[26];
        }
    }
    

    相关文章

      网友评论

          本文标题:力扣

          本文链接:https://www.haomeiwen.com/subject/cqpvgqtx.html