Solution accepted! But doubt persists. Please help! (fully commented solution)


  • 1
    Q
     class Solution {
     public:
    
    void addNextWord(string word, unordered_set<string>& wordDict, queue<string>& toVisit)
    {
        wordDict.erase(word);                             //erase every visited node
        
        for(int p=0; p<(int)word.length(); p++)
        {
            char letter = word[p];
            for(int i=0; i<26; i++)
            {
                word[p] = 'a' + i;                        //test for the word neighbours by replacing each of its alphabets
                
                if(wordDict.find(word)!=wordDict.end())   //if new word being formed by replacing p with each of the 26 alphabets is found
                {
                    toVisit.push(word);                             //add it to the queue
                    wordDict.erase(word);                           //delete it from dictionary
                }
            }
            word[p] = letter;                            //restore the word back
        }
    }
    
    
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) 
    {
        wordDict.insert(endWord);                   //add endword to the dictionary
        
        queue<string> toVisit;                      //make a queue for BFS
        addNextWord(beginWord, wordDict, toVisit);  //add to the queue, the neighbour of beginWord by using addNext function
        int dist = 2;
        while(!toVisit.empty())                     //while queue not empty
        {
            int num = toVisit.size();
            for(int i=0; i<num; i++)   //traverse all nodes of a level of BFS tree so formed
            {
                string word = toVisit.front();
                toVisit.pop();                      //pop the front word
                
                if(word == endWord)                 //if it is equal to endword, we have reached the end
                    return dist;
                addNextWord(word, wordDict, toVisit);   //else, add the next two neighbours
            }
            
            dist++;
        }
    }
    
    
    };
    

    Here, in the ladderLength() function, in the while loop, I am storing the length of the queue in an interger variable num, my solution is getting accepted.

            int num = toVisit.size();
            for(int i=0; i<num; i++)                                 //no problem
            {
                ......
            }
    

    But when, I combine this in the while loop and avoid taking an extra variable, I am getting error.

            for(int i=0; i<toVisit.size(); i++)                     //"a", "c", ["a", "b", "c"]  : test case fails
            {
                ......
            }
    

    please provide an explaination. Thanks in advance. :)


  • 7
    H

    Hi, I don't know if you have found the answer by yourself.

    When you get the toVisit.size() before for loop, you get the size of current level nodes, then you add next level node to the queue, that's the classical BFS algorithm.

    But if you combine it in the for loop, your queue is updated in each iteration. The size of queue changed too, and next iteration, your FOR loop's terminal condition is changed. Obveiously the algorithm out of our control :)

    Hope this explanation can help you :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.