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 optimization graph construction

Official solution: First, we label 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 this mapping; if not, the input has no solution. We can use a hash table to implement the above mapping.

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

Specifically, we can create virtual nodes. For the word hit, we create three virtual nodesit、ht, hi*, and let hit connect to these three virtual nodes with one edge each. 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 we added virtual nodes, the distance we get 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 half of 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;
    }
};