LeetCode211. 添加与搜索单词 - 数据结构设计(相关话题:Trie前缀树)
import java.util.TreeMap; class WordDictionary { private class Node{ public boolean isWord; public TreeMap<Character, Node> next; public Node(boolean isWord){ this.isWord = isWord; next = new TreeMap<>(); } public Node(){ this(false); } } private Node root; /** Initialize your data structure here. */ public WordDictionary() { root = new Node(); } /** Adds a word into the data structure. */ public void addWord(String word) { Node cur = root; for(int i = 0; i < word.length(); i++){ char c = word.charAt(i); if(cur.next.get(c) == null){ // 当前节点的next中是否存在字符c对应的下一个节点的映射 cur.next.put(c, new Node()); } cur = cur.next.get(c); } cur.isWord = 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) { return match(root, word, 0); } private boolean match(Node node, String word, int index){ if(index == word.length()){ return node.isWord; } char c = word.charAt(index); if(c != ‘.‘){ if(node.next.get(c) == null){ return false; } return match(node.next.get(c), word, index + 1); } // 等于‘.‘的情况是node的下一个字符的所有可能都去匹配 else{ for(char nextChar : node.next.keySet()){ if(match(node.next.get(nextChar), word, index + 1)){ return true; } } return false; } } } /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */
Solution bobo
相关推荐
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30