找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7785|回复: 4
收起左侧

[米群网刷题小分队] LeetCode新题 Add and Search Word - Data structure design 【Java】

[复制链接]

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
发表于 5-15-2015 11:20 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
字典树+dfs,难度不大。。。
class TrieNode {
                // Initialize your data structure here.
                boolean have;
                TrieNode[] children;

                public TrieNode() {
                        have = false;
                        children = new TrieNode[26];
                }
        }

        public class WordDictionary {
                private TrieNode root;

                public WordDictionary() {
                        root = new TrieNode();
                }

                // Adds a word into the data structure.
                public void addWord(String word) {
                        TrieNode cur = root;
                        int len = word.length();
                        for (int i = 0; i < len; i++) {
                                int c = word.charAt(i) - 'a';
                                if (cur.children[c] == null) {
                                        cur.children[c] = new TrieNode();
                                }
                                cur = cur.children[c];
                        }
                        cur.have = true;
                }

                // Returns if the word is in the data structure. A word could
                // contain the dot character '.' to represent any one letter.
                public boolean search(String word) {
                        TrieNode cur = root;
                        int len = word.length();
                        return dfs(root, word, 0, len);
                }

                private boolean dfs(TrieNode node, String word, int pos, int len) {
                        if (node == null || (pos == len && !node.have))
                                return false;
                        if (pos == len && node.have)
                                return true;
                        if (word.charAt(pos) == '.') {
                                for (int i = 0; i < 26; i++) {
                                        boolean re = dfs(node.children【i】, word, pos + 1, len);
                                        if (re)
                                                return re;
                                }
                                return false;
                        } else {
                                int c = word.charAt(pos) - 'a';
                                return dfs(node.children[c], word, pos + 1, len);
                        }
                }
        }

        // Your WordDictionary object will be instantiated and called as such:
        // WordDictionary wordDictionary = new WordDictionary();
        // wordDictionary.addWord("word");
        // wordDictionary.search("pattern");

50

主题

1

精华

303

积分

高级会员

Rank: 3Rank: 3

积分
303
发表于 5-16-2015 07:39 PM | 显示全部楼层
DFS 那里,能再优化嘛。。。偶不知道耶
回复 支持 反对

使用道具 举报

3

主题

0

精华

82

积分

资深会员

Rank: 2

积分
82
发表于 5-25-2015 04:04 PM | 显示全部楼层
Thanks for sharing!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表