Word Ladder: tìm đường ngắn nhất trong một graph không tồn tại trên giấy

Bạn không đang biến đổi từ. Bạn đang đi trên một graph mà mỗi node là một từ và mỗi cạnh nối hai từ khác nhau đúng một ký tự. Graph đó không được lưu ở đâu cả — nó tồn tại ngầm định trong cấu trúc của wordList — nhưng bài toán vẫn chỉ là "tìm đường ngắn nhất từ source đến destination trong unweighted graph." BFS giải được điều đó. Và nó luôn như vậy.

Cái hay là bạn xây dựng neighborhood của mỗi node ngay khi cần: với từ có độ dài M, bạn thử tất cả 26 * M hoán vị thay một ký tự và kiểm tra xem mỗi ứng viên có nằm trong dictionary hay không. Đó là toàn bộ thuật toán.

Đề bài

Cho hai từ beginWord và endWord cùng một dictionary wordList, tìm số lượng từ trong chuỗi biến đổi ngắn nhất từ beginWord đến endWord, trong đó mỗi bước chỉ thay đúng một ký tự và mọi từ trung gian phải tồn tại trong wordList; trả về 0 nếu không có chuỗi biến đổi nào. Full statement: LeetCode 127.

Ràng buộc:
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, và wordList[i] chỉ gồm chữ thường tiếng Anh.
- beginWord != endWord
- Tất cả các từ trong wordList là duy nhất.

Constraints nói gì

beginWord.length <= 10. Đây là điều đầu tiên cần chú ý. Sinh tất cả hàng xóm của một từ tốn O(M * 26) thao tác; với M = 10 đó là 260 ứng viên mỗi từ — rất nhẹ. Nếu M lên đến hàng trăm, bạn cần chiến lược sinh hàng xóm khác (ví dụ precompute wildcard pattern như *ot cho hot). Với M <= 10, brute-force thay từng ký tự là hoàn toàn ổn.

wordList.length <= 5000. Đó là số node trong graph. BFS thăm mỗi node nhiều nhất một lần, nên N = 5000 là hoàn toàn có thể xử lý. Cách tiếp cận O(N²) — kiểm tra tất cả các cặp từ để xác định adjacency trước — sẽ tốn 25 triệu thao tác, cũng ổn nhưng không cần thiết. Cách sinh hàng xóm on-the-fly tốn O(M * 26) mỗi lần dequeue, không phải O(N), tốt hơn khi N lớn so với M * 26.

Tất cả từ gồm chữ thường tiếng Anh. Alphabet có giới hạn (đúng 26 ký tự) nghĩa là bạn loop từ 'a' đến 'z' không cần xử lý đặc biệt gì thêm.

beginWord != endWord. Điều này loại trường hợp trivially-true ở cấp độ bài toán. Bạn không cần kiểm tra trong code, nhưng bạn cần kiểm tra early exit quan trọng hơn: nếu endWord không có trong wordList, trả về 0 ngay lập tức, vì không có chuỗi biến đổi hợp lệ nào có thể kết thúc tại một từ chưa bao giờ nằm trong dictionary.

Approach 1: BFS trên implicit word graph

Giải pháp canonical. Khởi tạo queue với (beginWord, 1) — từ bắt đầu và độ dài path hiện tại. Duy trì visited set để tránh thăm lại từ. Mỗi bước, dequeue một từ, sinh tất cả 26 * M hàng xóm, và enqueue bất kỳ hàng xóm nào nằm trong word_set và chưa được thăm. Ngay khi dequeue endWord, trả về level của nó. Nếu queue hết mà chưa tìm thấy, trả về 0.

Một chi tiết đúng đắn: đánh dấu từ là visited khi enqueue, không phải khi dequeue. Nếu chờ đến lúc dequeue, cùng một từ có thể được thêm vào queue nhiều lần từ các parent khác nhau, lãng phí thêm O(N) enqueue trong trường hợp xấu nhất. Path đầu tiên đến một từ cũng là path ngắn nhất (tính chất BFS), nên việc thăm lại không phục vụ mục đích gì.

from collections import deque
from typing import List
 
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
 
        word_set = set(wordList)
        queue = deque([(beginWord, 1)])
        visited = {beginWord}
 
        while queue:
            current_word, level = queue.popleft()
 
            if current_word == endWord:
                return level
 
            for i in range(len(current_word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = current_word[:i] + c + current_word[i + 1:]
                    if new_word in word_set and new_word not in visited:
                        visited.add(new_word)
                        queue.append((new_word, level + 1))
 
        return 0

using System.Collections.Generic;
 
public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        var wordSet = new HashSet<string>(wordList);
        if (!wordSet.Contains(endWord)) return 0;
 
        var queue = new Queue<(string word, int level)>();
        queue.Enqueue((beginWord, 1));
        var visited = new HashSet<string> { beginWord };
 
        while (queue.Count > 0) {
            var (currentWord, level) = queue.Dequeue();
 
            if (currentWord == endWord) return level;
 
            char[] chars = currentWord.ToCharArray();
            for (int i = 0; i < chars.Length; i++) {
                char original = chars[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    string newWord = new string(chars);
                    if (wordSet.Contains(newWord) && !visited.Contains(newWord)) {
                        visited.Add(newWord);
                        queue.Enqueue((newWord, level + 1));
                    }
                }
                chars[i] = original;
            }
        }
 
        return 0;
    }
}

Phiên bản C# dùng buffer char[] thay vì string concatenation, điều này có ý nghĩa nhỏ về performance vì string là immutable trong C# và concatenation cấp phát bộ nhớ mới. Trong Python, slice current_word[:i] + c + current_word[i+1:] là idiomatic và hoàn toàn ổn.

Trace tay qua Example 1

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

BFS mở rộng từng level:

Level 1:  dequeue "hit"
          hàng xóm: "hot" có trong word_set -> enqueue ("hot", 2)
          (tất cả thay thế khác không khớp word_set)

Level 2:  dequeue "hot"
          hàng xóm: "dot" có trong word_set -> enqueue ("dot", 3)
                     "lot" có trong word_set -> enqueue ("lot", 3)

Level 3:  dequeue "dot"
          hàng xóm: "dog" có trong word_set -> enqueue ("dog", 4)
          dequeue "lot"
          hàng xóm: "log" có trong word_set -> enqueue ("log", 4)

Level 4:  dequeue "dog"
          hàng xóm: "cog" có trong word_set -> enqueue ("cog", 5)
          dequeue "log"
          hàng xóm: "cog" đã trong visited -> bỏ qua

Level 5:  dequeue "cog" -> current_word == endWord -> return 5

Kết quả: 5. Path là hit -> hot -> dot -> dog -> cog.

Complexity

Time: O(M² * N). Với mỗi trong N từ, ta sinh M * 26 ứng viên hàng xóm. Xây dựng mỗi ứng viên tốn O(M) (string slicing hoặc copy char array). Vậy: N * M * 26 * M = O(M² * N). Trong thực tế BFS kết thúc sớm hơn, nhưng worst case là chuỗi dài qua tất cả N từ.

Space: O(M * N). word_set chứa N string mỗi cái dài M. visited set tương tự. Queue chứa nhiều nhất N entry, mỗi entry là string O(M).

Approach 2: Bidirectional BFS

BFS từ một đầu mở rộng frontier tăng xấp xỉ theo b^d trong đó b là branching factor (số hàng xóm mỗi từ) và d là độ dài đường ngắn nhất. Bidirectional BFS đồng thời mở rộng từ beginWord và endWord, gặp nhau ở giữa. Mỗi phía chỉ khám phá b^(d/2), nên tổng công việc xấp xỉ 2 * b^(d/2) thay vì b^d. Với graph lớn hoặc path dài, đây là speedup thực tế đáng kể dù asymptotic class vẫn như nhau.

Implementation dùng hai set — begin_set và end_set — thay vì queue. Mỗi iteration, ta mở rộng một set thêm một level. Điều kiện kết thúc: nếu hàng xóm được sinh ra xuất hiện trong set kia, hai frontier đã gặp nhau, và câu trả lời là level + 1.

Một tối ưu quan trọng: luôn mở rộng set nhỏ hơn. Kích thước của set lớn hơn cho thấy giới hạn trên về số hàng xóm ta sẽ sinh. Bằng cách luôn chọn phía nhỏ hơn, ta giảm thiểu công việc mỗi iteration.

from typing import List
 
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
 
        word_set = set(wordList)
        begin_set = {beginWord}
        end_set = {endWord}
        visited = set()
        level = 1
 
        while begin_set and end_set:
            # Luôn mở rộng frontier nhỏ hơn
            if len(begin_set) > len(end_set):
                begin_set, end_set = end_set, begin_set
 
            next_set = set()
            for word in begin_set:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        new_word = word[:i] + c + word[i + 1:]
 
                        if new_word in end_set:
                            return level + 1
 
                        if new_word in word_set and new_word not in visited:
                            visited.add(new_word)
                            next_set.add(new_word)
 
            begin_set = next_set
            level += 1
 
        return 0

using System.Collections.Generic;
 
public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        var wordSet = new HashSet<string>(wordList);
        if (!wordSet.Contains(endWord)) return 0;
 
        var beginSet = new HashSet<string> { beginWord };
        var endSet = new HashSet<string> { endWord };
        var visited = new HashSet<string>();
        int level = 1;
 
        while (beginSet.Count > 0 && endSet.Count > 0) {
            // Luôn mở rộng frontier nhỏ hơn
            if (beginSet.Count > endSet.Count) {
                var tmp = beginSet;
                beginSet = endSet;
                endSet = tmp;
            }
 
            var nextSet = new HashSet<string>();
            foreach (var word in beginSet) {
                char[] chars = word.ToCharArray();
                for (int i = 0; i < chars.Length; i++) {
                    char original = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        string newWord = new string(chars);
 
                        if (endSet.Contains(newWord)) return level + 1;
 
                        if (wordSet.Contains(newWord) && !visited.Contains(newWord)) {
                            visited.Add(newWord);
                            nextSet.Add(newWord);
                        }
                    }
                    chars[i] = original;
                }
            }
 
            beginSet = nextSet;
            level++;
        }
 
        return 0;
    }
}

Phiên bản bidirectional không theo dõi level bên trong queue entry. Thay vào đó, level là số nguyên tăng một lần mỗi vòng mở rộng đầy đủ. Khi hai frontier gặp nhau (new_word in end_set), câu trả lời là level + 1 vì phía hiện tại đã mở rộng level tầng và từ gặp nhau cách một bước vào vùng đã mở rộng của phía kia.

Complexity

Time: O(M² * N) tiệm cận — cùng bound — nhưng với hằng số nhỏ hơn. Trong worst case (không có path), ta vẫn duyệt tất cả các từ. Trong average case với path hợp lệ độ dài d, phiên bản bidirectional khám phá xấp xỉ 2 * b^(d/2) node so với b^d của standard BFS. Với b khoảng 26 * 10 = 260 và d = 5, đó là 2 * 260^2.5 ≈ 2.2M so với 260^5 ≈ 1.2 nghìn tỷ — bidirectional nhanh hơn không đo được trên graph sâu.

Space: O(M * N) — cùng class. Hai frontier set cộng visited, mỗi set chứa string dài M.

Các edge case cần biết

endWord không có trong wordList: trả về 0 ngay lập tức. Đây là kiểm tra đầu tiên trong cả hai giải pháp. Bỏ qua nó nghĩa là BFS sẽ cạn kiệt toàn bộ dictionary khi cố tìm đến mục tiêu không thể đạt.

Không có path nhưng endWord có trong wordList: BFS (hoặc bidirectional BFS) thoát hoàn toàn mà hai frontier không gặp nhau. Trả về 0. Ví dụ: beginWord = "hit", wordList = ["hot","dot","dog","lot","log"] không có "cog" — dù có các từ trung gian hợp lệ, bạn không thể đến endWord vì nó không có trong list.

beginWord chỉ cách endWord một substitution: đường ngắn nhất có độ dài 2. Lần dequeue đầu tiên trong BFS sinh endWord là hàng xóm và trả về ngay. Phiên bản bidirectional trả về level + 1 = 2 ở vòng mở rộng đầu tiên (level khởi tạo là 1). Cả hai xử lý đúng mà không cần special-case.

wordList = [endWord] mà thôi: nếu beginWord có thể đến endWord trong một bước, trả về 2. Ngược lại trả về 0. Không có từ trung gian nghĩa là hoặc có cạnh trực tiếp hoặc không có gì.

Đánh dấu visited khi dequeue thay vì enqueue: không sai về mặt correctness (BFS vẫn tìm được shortest path), nhưng chậm thảm khốc. Trong dense graph, cùng một từ có thể được enqueue từ O(N) parent khác nhau trước khi lần đầu tiên bị dequeue. Queue phình to đến O(N²) kích thước. Luôn đánh dấu khi enqueue.

Nên chọn approach nào khi phỏng vấn

Tôi chọn standard BFS. Khoảng 15-20 dòng, invariant rõ ràng (BFS tìm shortest path trong unweighted graph), và implementation dễ kiểm tra trên whiteboard. Với N = 5000 và M = 10, standard BFS đủ nhanh — nhiều nhất 5000 * 10 * 26 = 1.3M thao tác.

Bidirectional BFS là câu trả lời khi interviewer hỏi "bạn có thể làm tốt hơn không?" hoặc khi graph đủ sâu và rộng để standard BFS hiển nhiên là chậm. Ý tưởng chính cần phát biểu: bạn cắt frontier đang phát triển theo hàm mũ xuống một nửa bằng cách tấn công từ cả hai đầu. Tối ưu swap-set-nhỏ-hơn là chi tiết giúp nó hoạt động đúng trong thực tế.

Tôi sẽ không ship bidirectional BFS trong production mà không có comment giải thích invariant theo dõi level. Điều kiện kết thúc level + 1 là phần mà người ta dễ nhầm — một comment cẩn thận giúp người đọc tiếp theo tiết kiệm mười phút.

Bảng so sánh

Asymptotic class giống nhau. Sự khác biệt thực tế tăng theo hàm mũ với độ dài path.

Pattern có thể chuyển giao: implicit graph BFS

Word Ladder là template cho một lớp bài toán trong đó graph không bao giờ được lưu — chỉ quy tắc dẫn xuất hàng xóm mới quan trọng. State là một node; transition rule là hàm edge; BFS tìm chuỗi transition ngắn nhất.

Nhận ra pattern này là kỹ năng thực sự. Bất cứ khi nào bạn thấy "minimum steps", "shortest sequence", hay "minimum transformations" với quy tắc bước được xác định rõ, câu trả lời hầu như luôn là BFS trên implicit state graph.

Vị trí trong series graphs

Bốn bài trước — Number of Islands, Clone Graph, Course Schedule, và Rotting Oranges — đều hoạt động trên các graph được cho sẵn: adjacency list, grid với tọa độ trực tiếp, hoặc matrix đã xây dựng sẵn. Word Ladder là bài đầu tiên ở đây mà cấu trúc graph phải được dẫn xuất on-the-fly từ input domain. Đó là bước khái niệm tiến lên.

Hàng xóm của "hot" không được liệt kê ở đâu trong input. Bạn sinh chúng bằng cách thử mọi thay thế một ký tự một cách hệ thống. Đây là sự khác biệt giữa "duyệt graph đã cho" và "model bài toán của bạn thành graph rồi duyệt nó."

Minimum Genetic Mutation (433) là cùng bài toán, cùng cấu trúc, với alphabet bốn ký tự (A, C, G, T) và gene bank thay vì word list. Nếu bạn giải được Word Ladder, 433 về cơ bản là miễn phí.

Open the Lock (752) áp dụng cùng implicit-graph BFS cho khóa số. Các "từ" là chuỗi bốn chữ số, mỗi "ký tự" có thể quay lên hoặc xuống, và có các ô chết cần tránh. Branching factor là 8 (bốn vị trí, hai hướng mỗi vị trí), không gian state là 10^4 = 10000. Pure BFS, cùng pattern.

Word Ladder II (126) yêu cầu tất cả các đường ngắn nhất, không chỉ độ dài. Điều này thay đổi bài toán đáng kể — bạn không thể dừng tại lần đầu tiên đến endWord, bạn phải theo dõi tất cả parent pointer và tái tạo mọi shortest path. Cấu trúc BFS tương tự nhưng bookkeeping nặng hơn đáng kể. Nếu 127 cảm thấy thoải mái, 126 là thử thách tiếp theo tự nhiên.

Shortest Path with Alternating Colors (1129) thêm constraint về loại cạnh (mỗi bước phải luân phiên giữa cạnh đỏ và xanh), đòi hỏi state phải encode không chỉ node hiện tại mà còn màu cạnh cuối cùng đã dùng. Cùng implicit-graph BFS, nhưng state là (node, last_color) thay vì chỉ node.