127.Word Ladder

Tags: [BFS], [set]

Com: {fb}

Link: https://leetcode.com/problems/word-ladder/\#/description

Given two words (beginWordandendWord), and a dictionary's word list, find the length of shortest transformation sequence frombeginWordtoendWord, 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.

For example, Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]

As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length5.

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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution: BFS

from collections import deque

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        if not beginWord:
            return 0

        words = set(wordList)

        queue = deque()
        queue.append((beginWord, 0))
        visited = set()
        visited.add(beginWord)

        while queue:
            curr_w, curr_distance = queue.popleft()

            if curr_w == endWord:
                return curr_distance + 1

            curr_w_chars = list(curr_w)
            for i in xrange(len(curr_w_chars)):
                original_char = curr_w_chars[i]
                for c_code in xrange(ord('a'), ord('z') + 1):
                    new_c = chr(c_code)
                    if new_c == original_char:
                        continue

                    curr_w_chars[i] = new_c
                    new_w = ''.join(curr_w_chars)
                    if new_w not in visited and new_w in words:
                        visited.add(new_w)
                        queue.append((new_w, curr_distance + 1))

                curr_w_chars[i] = original_char

        return 0

Revelation:

• We can add the node to visited after queue.popleft(), and we also can add the node to visited set right before queue.append(), they have the same result, and both are correct, but add the node right before queue.append() will make the algorithm a little bit faster.

Note:

• Time complexity = O(len(wordList) * len(beginWord)), because we only add the node whose value is in the wordList into the queue.
• Space complexity = O(len(wordList)), there are at most len(wordList) + 1 nodes.