473. Add and Search Word

是Trie的扩展,难点在于有.可以匹配任意字符。在search的时候要利用DFS来做了。在创建和查找Trie的基础上做即可,需要注意的坑如下:

  1. 插入新单词前可以先search下,如果已存在就不要再添加了。
  2. 找错误,为什么下面这段代码错了,错在哪里?

public boolean helper(String word, int index, TrieNode node){
 char c = word.charAt(index);
 if(c==’.’){
 for(Map.Entry<Character, TrieNode> entry : node.children.entrySet()){
 TrieNode next = entry.getValue();
 
 if(index == word.length()-1){
 return next.isword;
 }
 else{
 return helper(word, index+1, next);
 } } }
 
 if(node.children.containsKey(c)){
 TrieNode next = node.children.get(c);
 
 if(index == word.length()-1){
 return next.isword;
 }
 else{
 return helper(word, index+1, next);
 }
 }
 
 return false;

}

错在在对.的DFS部分,如果直接就返回next.isword的话,就不会达到查看所有的子结点的效果,而是遇到hashmap里面第一个key的时候,返回其isword属性就结束了,这当然是不对的。那好吧,那就改成这个样子:

boolean result = false;

if(c==’.’){
 
 for(Map.Entry<Character, TrieNode> entry : node.children.entrySet()){
 TrieNode next = entry.getValue();
 
 if(index == word.length()-1 && next.isword){
 result = true;
 }
 else{
 if( helper(word, index+1, next)){
 result = true;
 }
 }
 
 }
 return result;
 }

下面的非.部分没有变化。这样对了么?

还是不对,因为如果index确实是word.length-1 但是 next.isword还是false的情况,还会继续运行下去,即会运行helper(word, index+1, next)而造成越界,因为index+1会超过字符串长度。

应该改成如下 ,其他不变。

if(index == word.length()-1){
 if(next.isword){
 result = true; //见好就收
 }
 else{
 continue; // 不能递归继续看下一位了,因为index已经到底。所以continue一下去遍历下一个hashmap的元素把。
 }
 }

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.