Interview Classic 150 Questions P127 Word Ladder

---

Timeline

Timeline

2025-11-24

init

BFS

---

Problem:

P127 Word Ladder

https://leetcode.cn/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

BFS brute-force enumeration, this is the method I first thought of, but it is very inefficient.

BFS brute-force enumeration

#include <string>
#include <queue>
#include <unordered_set>
#include <vector>

using std::string;
using std::unordered_set;
using std::vector;
using std::queue;

class Solution {
    private:
	bool is_neighbor(string word, string possible_neighbor)
	{
		int diff_cnt = 0, n = word.size();
		if (possible_neighbor.size() != n) {
			return false;
		}
		for (int i = 0; i < n; i++) {
			if (word[i] != possible_neighbor[i]) {
				diff_cnt++;
			}
			if (diff_cnt > 1) {
				return false;
			}
		}
		return true;
	}

    public:
	int ladderLength(string beginWord, string endWord, vector<string> &wordList)
	{
		int i, n, level = 1;
		queue<string> que;

		unordered_set<string> visited;
		string curr_word;

		que.push(beginWord);
		visited.insert(beginWord);

		while (!que.empty()) {
			n = que.size();

			for (i = 0; i < n; i++) {
				curr_word = que.front();
				que.pop();
				if (curr_word == endWord) {
					return level + 1;
				}
				for (auto &possible_neighbor : wordList) {
					if (!visited.count(possible_neighbor) &&
					    is_neighbor(curr_word, possible_neighbor)) {
						que.push(possible_neighbor);
						visited.insert(possible_neighbor);
					}
				}
			}
			level++;
		}
		return 0;
	}
};

BFS + virtual node optimized graph construction

Official solution: First, we assign a label to each word, i.e., assign an id to each word. Create a mapping wordId from word to id, and add beginWord and all words in wordList to this mapping. Then we check whether endWord is in the mapping; if not, the input has no solution. We can use a hash table to implement the above mapping.

Then we need to build the graph. Based on the naive approach, we can enumerate every pair of words and check whether they differ by exactly one character to determine whether the nodes corresponding to these two words can be connected. But this is too inefficient, so we can optimize the graph construction.

Specifically, we can create virtual nodes. For the word hit, we create three virtual nodes it、ht, hi* and connect hit to each of these three virtual nodes with an edge. If a word can be transformed into hit, then that word will necessarily connect to one of these three virtual nodes. For each word, we enumerate the virtual nodes it connects to, and connect the id corresponding to that word with the ids corresponding to these virtual nodes.

Finally, we add the starting point to the queue and start breadth-first search. When we reach the end point, we have found the length of the shortest path. Note that because virtual nodes are added, the distance we obtain is twice the actual shortest path length. Also, we did not count the contribution of the starting point to the answer, so we should return the result of half the distance plus one.

class Solution {
public:
    unordered_map<string, int> wordId;
    vector<vector<int>> edge;
    int nodeNum = 0;

    void addWord(string& word) {
        if (!wordId.count(word)) {
            wordId[word] = nodeNum++;
            edge.emplace_back();
        }
    }

    void addEdge(string& word) {
        addWord(word);
        int id1 = wordId[word];
        for (char& it : word) {
            char tmp = it;
            it = '*';
            addWord(word);
            int id2 = wordId[word];
            edge[id1].push_back(id2);
            edge[id2].push_back(id1);
            it = tmp;
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for (string& word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.count(endWord)) {
            return 0;
        }
        vector<int> dis(nodeNum, INT_MAX);
        int beginId = wordId[beginWord], endId = wordId[endWord];
        dis[beginId] = 0;

        queue<int> que;
        que.push(beginId);
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int& it : edge[x]) {
                if (dis[it] == INT_MAX) {
                    dis[it] = dis[x] + 1;
                    que.push(it);
                }
            }
        }
        return 0;
    }
};