LeetCode 127. Word Ladder

题目

原题在此
Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Return 0 if there is no such transformation sequence.

Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Constraints:

• 1 <= beginWord.length <= 100
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the strings in wordList are unique.

解析

根据题意,例如”hit”可以转变成”hot”, 在图(抽象数据结构)中称作节点hit和节点hot有一条边相连.
如何确定两个节点是不是邻居:

1. 把wordList 数组丢到 set 里方便快速查找.
2. 对word的每个字符用a-z替换并查看是否在set中(不包括自己),如果在就是邻居. 以hit为例: ait, bit, … zit, bat, bbt, … bzt, bia …

所以题目转化为根据数组构造一个图,然后搜索起点到终点的最短路径.
这时你就想到了BFS. BFS的要点:

1. 用queue(FIFO)的数据结构逐层遍历.
2. 图中可能有环, 需要用set或map之类的关联容器快速查找结点是否已经访问过. 访问过则不做处理, 否则会死循环.

在本题中, 由于起点终点已知, 只搜索最短路径, 可以使用双向BFS来优化. 双向BFS的要点:

1. bfs中使用的queue和set一分为二, 首尾各自保存. 循环终止判断变为当前元素是否在另一个集合里出现过.
2. 当前集合中有较多节点的集合, 在下一层的遍历中有更大的可能性遇到更多的节点. 所以根据当前集合的大小首尾交换.

代码

/* C++ BFS */
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        int length = 1;
        while (!todo.empty()) {
            int n = todo.size();
            for (int i = 0; i < n; i++) {
                string word = todo.front();
                todo.pop();
                if (word == endWord) {
                    return length;
                }
                dict.erase(word);
                for (int j = 0; j < word.size(); j++) {
                    char c = word[j];
                    for (int k = 0; k < 26; k++) {
                        word[j] = 'a' + k;
                        if (dict.find(word) != dict.end()) {
                            todo.push(word);
                        }
                     }
                    word[j] = c;
                }
            }
            length++;
        }
        return 0;
    }
};

/* Golang Bidirectional BFS */
func ladderLength(beginWord string, endWord string, wordList []string) int {
    wordIdx := make(map[string]int)
    endUsed := make([]bool, len(wordList))
    
    for i, v := range wordList {
        wordIdx[v] = i
    }
    
    if idx, ok := wordIdx[endWord]; ok {
        endUsed[idx] = true;
    } else {
        return 0
    }
    
    var step int = 0
    startUsed := make([]bool, len(wordList))
    sq, eq := list.New(), list.New()
    
    sq.PushBack(beginWord)
    eq.PushBack(endWord)
    
    for sq.Len() > 0 {
        step++
        length := sq.Len()
        for i := 0; i < length; i++ {
            bytes := []byte(sq.Remove(sq.Front()).(string))
            for j := 0; j < len(bytes); j++ {
                b := bytes[j]
                for c := byte('a'); c <= 'z'; c++ {
                    if c != b {
                        bytes[j] = c
                        if idx, ok := wordIdx[string(bytes)]; ok {
                            if endUsed[idx] {
                                return step + 1
                            } else {
                                if !startUsed[idx] {
                                    sq.PushBack(wordList[idx])
                                    startUsed[idx] = true
                                }
                            }
                        }
                    }
                
                }
                bytes[j] = b
            }
        }
        if sq.Len() > eq.Len() {
            sq, eq = eq, sq
            startUsed, endUsed = endUsed, startUsed
        }
    }
    return 0
}