首页 > 其他 > 详细

Add and Search Word - Data structure design

时间:2015-06-01 11:05:05      阅读:368      评论:0      收藏: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.

思路:

  前缀树+回溯

我的代码:

技术分享
public class WordDictionary {

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    public void addWord(String word) {
        HashMap<Character, TrieNode> children = root.children;
        for(int i=0; i<word.length(); i++)
        {
            TrieNode node;
            char c = word.charAt(i);
            if(children.containsKey(c)) node = children.get(c);
            else
            {
                node = new TrieNode(c);
                children.put(c,node);
            }
            children = node.children;
            if(i == word.length()-1)
            {
                node.isWord = true;
            }
        }
    }
    public boolean search(String word) {
        if(word==null || word.length()==0)    return true;
        HashMap<Character, TrieNode> children = root.children;
        return helperSearch(word, children);
        
    }
    public boolean helperSearch(String word, HashMap<Character, TrieNode> hash)
    {
        if(word.length() == 1)
        {
            char c = word.charAt(0);
            if(c == ‘.‘)
            {
                for(char key : hash.keySet())
                {
                    if(hash.get(key).isWord) return true;
                }
                return false;
            }
            else
            {
                if(hash.containsKey(c))        return hash.get(c).isWord;
                else return false;
            }
        }
        if(word.charAt(0) == ‘.‘)
        {
            for(char c: hash.keySet())
            {
                if(helperSearch(word.substring(1), hash.get(c).children))   return true;   
            }
            return false;
        }
        else
        {
            char c = word.charAt(0);
            if(hash.containsKey(c))
            {
                return helperSearch(word.substring(1), hash.get(c).children);
            }
            else return false;
        }
    }
    class TrieNode {
        public TrieNode() {
        }
        public TrieNode(char c) {
            this.c = c;
        }
        char c;
        HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();  
        boolean isWord;
    }
}
View Code

学习之处:

  • 之前做了前缀树的解法,很自然的考虑到了回溯的解法,一遍AC了

Add and Search Word - Data structure design

原文:http://www.cnblogs.com/sunshisonghit/p/4543293.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!