-1

私が尋ねたこの質問を参照して：トライで最も長い単語を見つける方法は？

回答に示されている擬似コードの実装に問題があります。

findLongest(trie):
 //first do a BFS and find the "last node"
 queue <- []
 queue.add(trie.root)
 last <- nil
 map <- empty map
while (not queue.empty()):
 curr <- queue.pop()
 for each son of curr:
    queue.add(son)
    map.put(son,curr) //marking curr as the parent of son
 last <- curr
//in here, last indicate the leaf of the longest word
//Now, go up the trie and find the actual path/string
curr <- last
str = ""
while (curr != nil):
      str = curr + str //we go from end to start   
    curr = map.get(curr)
return str

これは私が私の方法のために持っているものです

public static String longestWord (DTN d) {
  Queue<DTN> holding = new ArrayQueue<DTN>();
  holding.add(d);
  DTN last = null;
  Map<DTN,DTN> test = new ArrayMap<DTN,DTN>();
  DTN curr;
  while (!holding.isEmpty()) {
       curr = holding.remove();

      for (Map.Entry<String, DTN> e : curr.children.entries()) {
          holding.add(curr.children.get(e));
          test.put(curr.children.get(e), curr);
      }
          last = curr;

      }
  curr = last;
  String str = "";
  while (curr != null) {
      str = curr + str;
      curr = test.get(curr);

  }
  return str;

  }

次の場所でNullPointerExceptionが発生します：

 for (Map.Entry<String, DTN> e : curr.children.entries())

メソッドのNullPointerExceptionの原因を見つけて修正し、トライで最長の単語を返すようにするにはどうすればよいですか？

4

2 に答える 2

1

curr.children.entries()それがnull値でないことを確認してください。おそらく、DTNそのノードに子がない場合はnull値を返します。これにより、が発生しますNullPointerException。

反復を開始する前に、簡単なチェックを行ってみてください。

if(curr.children.entries() != null)
{
    //It's safe, so procede with going deeper into the trie.
}
于 2012-11-04T04:43:13.323 に答える
1

@Clarkの回答に加えて、間接参照する前にcurr.childrenがnullでないことを確認してください。

于 2012-11-04T04:57:47.123 に答える