关于word ladder这道题目， 请教for loop

https://leetcode.com/problems/word-ladder/

以下是我的解法， 然而用comment掉的那句for (int i=0; i<q.size(); i++) 结果就不对了， 用for (int size = q.size(); size > 0; size--) 就对， 我打印了一下计数值并没什么区别， 哪位大神能告诉我一下这是为什么呀。。。已经被整懵了... thanks!

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord))
        {
            return 0;
        }

        queue<string> q;
        q.push(beginWord);

        int len=beginWord.length();
        int step=0;
        int count=0;

        while (!q.empty())
        {
            step++;
           //for (int i=0; i<q.size(); i++) //incorrect
           for (int size = q.size(); size > 0; size--)   //correct
            {
                string w=q.front();
                q.pop();
               count++;
               cout<<"count:"<<count<<endl;

                for (int j=0; j<len; j++)
                {
                    char ch=w[j];
                    for (int k='a'; k<='z'; k++)
                    {
                        w[j]=k;
                        if (w==endWord)
                        {
                            return step+1;
                        }
                        if (!dict.count(w))
                        {
                            continue;
                        }
                        dict.erase(w);
                        q.push(w);
                    }
                    w[j]=ch;
                }

            }
        } //end of while

        return 0;
    }
};

-------
input:

"hit"
"cog"
["hot","dot","dog","lot","log","cog"]

output:4
expected: 5

stdout:count:1
count:2
count:3
count:4
count:5

for loop里面，queue执行了push操作，queue的size在变。

我做BSF的时候，我喜欢把level/step 也放进queue里，

queue<pair<T, integer>> q;  T 在这道题里面就是String， Integer是level/step

如果这样做了以后，就不需要nested for loop.

1. Pair current = q.poll();
   
2. q.push(new Pair(next(current.first), current.second + 1));

复制代码

这样写的话，代码会简洁一些

hoooga 发表于 2020-6-28 16:14
for loop里面，queue执行了push操作，queue的size在变。

Got it, thanks!

david_smith 发表于 2020-6-28 22:17
我做BSF的时候，我喜欢把level/step 也放进queue里，

queue q;  T 在这道题里面就是String， Integer是l ...

This is a good solution, thanks for sharing!