Word Ladder -- Leetcode

[Question]

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time 
2. Each intermediate word must exist in the dictionary 

For example,

Given:

• start = "hit"
• end = "cog"
• dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence. 
• All words have the same length. 
• All words contain only lowercase alphabetic characters.

[Analysis]

The dictionary of words composed a word graph where two nodes of words are (bi-directionally, undirected) connected when there is only one character difference between two words: for example, "hot" and "dot". 

A BFS (Breadth First Search) will give the shortest path between two nodes in a graph. Please note, there is no need to construct the graph physically -- that will be time-consuming. Using Set/unordered_set can give the siblings of a node, which is sufficient to get the result.

Another catch is, how to find the sibling words of a given word. The straightforward solution is to compare the given word with every word unvisited in dictionary. The comparison will be costly when the dictionary is large (O(N), N is the number of words in dictionary). Due to the assumptions in the question, the number of possible sibling words is 25*L, where L is the length of the word -- see "getUnvisitedSiblings()" below.

[Solution]
//-- C++ --
class Solution {
    unordered_set<string> getUnvisitedSiblings( string& str, unordered_set<string>& unvisited ) {
        unordered_set<string> rslt;
        for (int i=0; i<str.size(); i++) {
            string tmp = str;
            for (char c='a'; c<='z'; c++) {
                tmp[i] = c;
                if (unvisited.count(tmp))
                    rslt.insert( tmp );
            }
        }
        return rslt;
    } 

public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        unordered_set<string> unvisited(wordList.begin(), wordList.end());
        unvisited.erase(beginWord); //make sure no redundant steps.
    
        q.push( beginWord );
        int len = q.size();    //size of current queue.
       
        int step = 1;
        while (!q.empty() && q.front()!=endWord) {
            string cur = q.front();
            q.pop(), len--;
           
            unordered_set<string> siblings = getUnvisitedSiblings( cur, unvisited );
            for (auto s: siblings) {
                q.push(s);
                unvisited.erase(s);
            }
        
            if (len==0) { // new level of BFS is reached.
                step++;
                len = q.size();
            }
        }

        if (!q.empty() && q.front()==endWord) return step;
        return 0;       
    }
};