刷题问题——问题出在哪里？

问题：127. Word Ladder

1. class Solution {
   
2.     public int ladderLength(String beginWord, String endWord, List<String> wordList) {
   
3.         Queue<String> q = new LinkedList<>();
   
4.         HashSet<String> visited = new HashSet<>();
   
5.         HashSet<String> dict = new HashSet<>();
   
6.         for(int i = 0; i< wordList.size(); i++){
   
7.             dict.add(wordList.get(i));
   
8.         }
   
9.         int level =1;
   
10.         q.add(beginWord);
    
11.         visited.add(beginWord);
    
12.         while(!q.isEmpty()){
    
13.             level++;
    
14.             
    
15.             for(int j=0; j< q.size(); j++){
    
16.                String str = q.poll();
    
17.                 for(int k = 0; k<str.length();k++){
    
18.                     char [] chars = str.toCharArray();
    
19.                     for(char c = 'a'; c <= 'z'; c++){   
    
20.                     chars [k] = c;
    
21.                     String word = new String(chars);
    
22.                     if(word.equals(endWord)&& dict.contains(word)){
    
23.                         return level;
    
24.                     }
    
25.                     if(dict.contains(word) && !visited.contains(word)){
    
26.                         q.add(word);
    
27.                         visited.add(word);
    
28.                         }
    
29.                     }
    
30.                 }
    
31.             }
    
32.         }
    
33.         return 0;
    
34.     }
    
35. }

复制代码

------------debug 信息-------------------

beginWord: "hit"
endWord: "cog"
wordList: ["hot","dot","dog","lot","log","cog"]
q: ["dot","lot"]
visited: [lot, hit, dot, hot]
dict: [lot, log, dot, cog, hot, dog]
level: 3
j: 0


beginWord: "hit"
endWord: "cog"
wordList: ["hot","dot","dog","lot","log","cog"]
q: ["lot","dog"]
visited: [lot, hit, dot, hot, dog]
dict: [lot, log, dot, cog, hot, dog]
level: 3
j: 1

beginWord: "hit"
endWord: "cog"
wordList: ["hot","dot","dog","lot","log","cog"]
q: ["lot","dog"]
visited: [lot, hit, dot, hot, dog]
dict: [lot, log, dot, cog, hot, dog]
level: 3

我觉得是["dot", "lot"]这个level上出问题，我觉得我自己陷入一个我自己觉得没问题，但是代码打出来有问题。帮忙点出来我错在哪里？谢谢

不明觉厉，可能q.size()吧

for loop之前要把q.size() 记录下来，int size = q.size(). 然后for(int j=0; j < size; j++). 因为你在for loop里还有q.add() operation这样的话q.size()就会一直更新。建议lz刷一下level order traversal, 把bfs模板好好研究一下。

duziyuanyang 发表于 2019-12-14 09:25
for loop之前要把q.size() 记录下来，int size = q.size(). 然后for(int j=0; j < size; j++). 因为你在for ...

明白了。 没注意到这个细节，谢谢

swimmingfish96 发表于 2019-12-14 04:10
不明觉厉，可能q.size()吧

你这是委婉给提示么？

在遍历队列过程中增删元素经常会造成错误，可以用iterator遍历

养成好习惯，循环跳出条件使用常量，不要用数组长度，可以避免这种问题

wangdiao01 发表于 2019-12-14 14:29
养成好习惯，循环跳出条件使用常量，不要用数组长度，可以避免这种问题

谢谢提醒