# 127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

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.

# Solution

Approach 1: one-directional BFS. Time: O(N * L) where N == len(wordList) and L == len(beginWord).

Approach 2: bi-directional BFS.

# Code (Python)

Approach 1:

    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        word_list = set(wordList)
        if endWord not in word_list or len(beginWord) != len(endWord):
            return 0
        cur_words = [beginWord]
        level = 1
        while cur_words:
            level += 1
            # accumulate words at the next level
            new_words = []
            for word in cur_words:
                # can also enumerate the whole word_list to see if diff == 1, but it takes N*L time
                # this takes 26 * L time
                for i in range(len(word)):
                    for letter in 'abcdefghijklmnopqrstuvwxyz':
                        if letter == word[i]:
                            continue
                        new_word = ''.join([word[:i], letter, word[i+1:]])
                        if new_word in word_list:
                            if new_word == endWord:
                                return level
                            # deduplication: mark as visited to avoid cycles
                            word_list.remove(new_word)
                            new_words.append(new_word)   
            cur_words = new_words
        return 0

Approach 2:

    def ladderLength(self, beginWord, endWord, wordList):
        word_list = set(wordList)
        if endWord not in word_list or len(beginWord) != len(endWord):
            return 0
        if beginWord == endWord:
            return 1
        # dedup: need to make sure the front tier (to be explored) is not in word_list
        word_list.discard(beginWord)
        front, back = set([beginWord]), set([endWord]) # use set operations as much as possible
        level = 2
        while front:
            front = word_list & set([
                ''.join([word[:i], letter, word[i+1:]])
                for i in range(len(beginWord))
                for word in front
                for letter in 'abcdefghijklmnopqrstuvwxyz'
            ])
            if front & back: # has intersection
                return level
            level += 1
            if len(back) < len(front):
                front, back = back, front
            # also dedup: exclude the front tier, but the back tier need to be included otherwise we can't find intersections
            word_list -= front
        return 0

# Code (C++)

Approach 1:

// BFS.
class Solution {
private:
    bool isTransformable(string a, string b)
    {
        if (a.size() != b.size())
            return false;
        int count = 0;
        for (int i = 0; i < a.size(); ++i)
        {
            if (a[i] != b[i])
                count++;
            if (count > 1)
                return false;
        }
        return count == 1;
    }
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        bool visited[wordList.size()] = {false};
        queue<string> q;
        q.push(beginWord);
        int level = 1;
        while (!q.empty())
        {
            level++;
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i)
            {
                string curr = q.front();
                q.pop();
                for (int j = 0; j < wordList.size(); ++j)
                {
                    if (!visited[j] && isTransformable(curr, wordList[j]))
                    {
                        if (wordList[j] == endWord)
                            return level;
                        q.push(wordList[j]);
                        visited[j] = true;
                    }
                }
            }
        }
        return 0;
    }
};

Approach 2:

// Bidirectional BFS.
class Solution {
private:
    bool isTransformable(string a, string b)
    {
        if (a.size() != b.size())
            return false;
        int count = 0;
        for (int i = 0; i < a.size(); ++i)
        {
            if (a[i] != b[i])
                count++;
            if (count > 1)
                return false;
        }
        return count == 1;
    }
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int i;
        for (i = 0; i < wordList.size(); ++i)
        {
            if (wordList[i] == endWord)
                break;
        }
        if (i == wordList.size())
            return 0;
        int visited[wordList.size()] = {0};
        visited[i] = 2; // endWord is already visited.
        queue<string> q1, q2;
        q1.push(beginWord);
        q2.push(endWord);
        int level1 = 1;
        int level2 = 1;
        while (!q1.empty() && !q2.empty())
        {
            int q1Size = q1.size();
            for (int i = 0; i < q1Size; ++i)
            {
                string curr = q1.front();
                q1.pop();
                for (int j = 0; j < wordList.size(); ++j)
                {
                    if (visited[j] != 1 && isTransformable(curr, wordList[j]))
                    {
                        if (visited[j] == 2)
                            return level1 + level2;
                        q1.push(wordList[j]);
                        visited[j] = 1;
                    }
                }
            }
            level1++;
            int q2Size = q2.size();
            for (int i = 0; i < q2Size; ++i)
            {
                string curr = q2.front();
                q2.pop();
                for (int j = 0; j < wordList.size(); ++j)
                {
                    if (visited[j] != 2 && isTransformable(curr, wordList[j]))
                    {
                        if (visited[j] == 1)
                            return level1 + level2;
                        q2.push(wordList[j]);
                        visited[j] = 2;
                    }
                }
            }
            level2++;
        }
        return 0;
    }
};