Super easy BFS driven C++ Solution


  • 1
    A

    BFS always guaranteed to produce shortest path between two nodes in a graph. Here we use one-sided BFS to reach endWord From beginWord. We keep a map named "prev" to construct the path(length) once endWord is reached.

    class Solution {
        int calcLen(map<string, string> &prev, string beginWord, string endWord)
        {
            string cur = prev.find(endWord)->second;
            int len = 1;
            
            while(cur != beginWord)
            {
                cur = prev.find(cur)->second;
                len++;
            }
            
            return len+1;
        }
        
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            
            if(beginWord.compare(endWord) == 0) return 0;
            
            map<string, string> prev;
            
            queue<string> bfs;
            bfs.push(beginWord);
            
            while(!bfs.empty())
            {
                string s = bfs.front();
                bfs.pop();
                
                string s2(s);
                
                for(int i = 0; i < s.length(); i++)
                {
                    char c = s[i];
    
                    for(char j = 'a'; j <= 'z'; j++)
                    {
                        if(c != j)
                        {
                            s[i] = j;
    
                            if(wordList.find(s) != wordList.end()
                               && prev.find(s) == prev.end())
                            {
                                prev[s] = s2;
                                if(s.compare(endWord) == 0)
                                {
                                    return calcLen(prev, beginWord, endWord);
                                }
                                else
                                {
                                    bfs.push(s);
                                }
                            }
                            
                            s[i] = c;
                        }
                    }
                }
            }
            return 0;
        }
    };
    
    

Log in to reply
 

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