298,添加与搜索单词 - 数据结构设计

设计一个支持以下两种操作的数据结构:

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

答案:

 1public class WordDictionary {
2    public class TrieNode {
3        public TrieNode[] children = new TrieNode[26];
4        public String item = "";
5    }
6
7    private TrieNode root = new TrieNode();
8
9    public void addWord(String word) {
10        TrieNode node = root;
11        for (char c : word.toCharArray()) {
12            if (node.children[c - 'a'] == null) {
13                node.children[c - 'a'] = new TrieNode();
14            }
15            node = node.children[c - 'a'];
16        }
17        node.item = word;
18    }
19
20    public boolean search(String word) {
21        return match(word.toCharArray(), 0, root);
22    }
23
24    private boolean match(char[] chs, int k, TrieNode node) {
25        if (k == chs.length)
26            return !node.item.equals("");
27        if (chs[k] != '.') {
28            return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
29        } else {
30            for (int i = 0; i < node.children.length; i++) {
31                if (node.children[i] != null) {
32                    if (match(chs, k + 1, node.children[i])) {
33                        return true;
34                    }
35                }
36            }
37        }
38        return false;
39    }
40}

解析:

代码比较简单,如果对字典树比较熟悉的话,这题很容易理解,TrieNode可以把它当做一个发散的链表,只是在链表的结尾存储单词,其他节点不存储。

上一篇:07 SpringBoot之Profile文件


下一篇:wifi基本知识---总结