127

127. Word Ladder (Hard)

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.

Related Topics:
Breadth-first Search

Similar Questions:

• Word Ladder II (Hard)
• Minimum Genetic Mutation (Medium)

Solution 1. BFS

Since we are looking for the shortest path, BFS should be our first option.

Given a word w, we can try to change each w[i] to a character from 'a' to 'z'.

Once we found a neighbor word v, we remove v from the word list and push it to the queue.

Time Complexity

In the worst case we need to visit all the N words in A. For each word, we check all its 26W neighbors, and copy them to queue (the copying takes O(W) time), so addNeighbors takes O(W^2) time.

Thus, overall it takes O(N * W^2) time

// OJ: https://leetcode.com/problems/word-ladder/
// Author: github.com/lzl124631x
// Time: O(N * W^2)
// Space: O(NW)
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> s(begin(wordList), end(wordList));
        if (s.count(endWord) == 0) return 0;
        queue<string> q{{beginWord}};
        s.erase(beginWord);
        int step = 1;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto u = q.front();
                q.pop();
                if (u == endWord) return step;
                for (char &c : u) { // add unvisited neighbors of `u`
                    char tmp = c;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        if (tmp == ch) continue;
                        c = ch;
                        if (s.count(u) == 0) continue;
                        s.erase(u);
                        q.push(u);
                    }
                    c = tmp;
                }
            }
            ++step;
        }
        return 0;
    }
};

Solution 2. Bi-directional BFS

// OJ: https://leetcode.com/problems/word-ladder/
// Author: github.com/lzl124631x
// Time: O(N * W^2)
// Space: O(NW)
class Solution {
public:
    int ladderLength(string B, string E, vector<string>& A) {
        unordered_set<string> head, tail, s(begin(A), end(A));
        if (s.count(E) == 0) return 0;
        head.insert(B);
        tail.insert(E);
        s.erase(B);
        s.erase(E);
        int ans = 2;
        while (head.size() && tail.size()) {
            if (head.size() > tail.size()) swap(head, tail);
            unordered_set<string> next;
            for (auto w : head) {
                for (char &c : w) {
                    char tmp = c;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        c = ch;
                        if (tail.count(w)) return ans;
                        if (s.count(w) == 0) continue;
                        next.insert(w);
                        s.erase(w);
                    }
                    c = tmp;
                }
            }
            ++ans;
            swap(head, next);
        }
        return 0;
    }
};