LeetCode: Word Ladder – Prepare For Coder Interview

Word Ladder

Similar Problems:

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:

Only one letter can be changed at a time.
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 length 5.

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: bidirectional BFS

// https://code.dennyzhang.com/word-ladder
// https://code.dennyzhang.com/word-ladder
// Basic Ideas: bidirectional bfs
//
// Complexity: Time O(m*n) Space O(m*n)
func ladderLength(beginWord string, endWord string, wordList []string) int {
    words := map[string]bool{}
    visited1 := map[string]bool{}
    visited2 := map[string]bool{}
    for _, word := range wordList {
        words[word] = true
        visited1[word] = false
        visited2[word] = false
    }
    // check whether endWord is a transformed word
    if _, ok := words[endWord]; !ok {
        return 0
    }
    queue1 := []string{beginWord}
    visited1[beginWord] = true

    queue2 := []string{endWord}
    visited2[endWord] = true

    level := 2
    for len(queue1) > 0 && len(queue2) > 0 {
        if len(queue2) < len(queue1) {
            queue1, queue2 = queue2, queue1
            visited1, visited2 = visited2, visited1
        }
        // bfs from queue1
        l := []string{}
        for _, word := range queue1 {
            bytes := []byte(word)
            for i, ch := range bytes {
                for ch2:='a'; ch2<='z'; ch2++ {
                    // backtracking
                    bytes[i] = byte(ch2)
                    word2 := string(bytes)
                    if word2 != word {
                        // word exists, and not visited
                        if _, ok := words[word2]; ok && !visited1[word2] {
                            if visited2[word2] {
                                return level
                            }
                            l = append(l, word2)
                            // mark node as visited
                            visited1[word2] = true
                        }
                    }
                    bytes[i] = ch
                }
            }
        }
        queue1 = l
        level++
    }
    return 0
}

Solution: BFS in golang

// https://code.dennyzhang.com/word-ladder
// Basic Ideas: bfs + backtracking
//
//  Backtracking: we can only change one character at one time
//
// Complexity: Time O(m*n) Space O(m*n)
func ladderLength(beginWord string, endWord string, wordList []string) int {
    visited := map[string]bool{}
    for _, word := range wordList {
        visited[word] = false
    }
    // check whether endWord is a transformed word
    if _, ok := visited[endWord]; !ok {
        return 0
    }
    queue := []string{beginWord}
    level := 1
    for len(queue) > 0 {
        l := []string{}
        for _, word := range queue {
            bytes := []byte(word)
            for i, ch := range bytes {
                for ch2:='a'; ch2<='z'; ch2++ {
                    // backtracking
                    bytes[i] = byte(ch2)
                    word2 := string(bytes)
                    if word2 != word {
                        // word exists, and not visited
                        if _, ok := visited[word2]; ok && !visited[word2] {
                            if word2 == endWord {
                                return level+1
                            }
                            l = append(l, word2)
                            // mark node as visited
                            visited[word2] = true
                        }
                    }
                    bytes[i] = ch
                }
            }
        }
        queue = l
        level++
    }
    return 0
}

Solution: BFS in python

## https://code.dennyzhang.com/word-ladder
## Basic Ideas: BFS. Find the shortest path from point1 to point2
##
##      How fast we can find the next neighbors?
##      Let's say n = len(wordList), w=len(word)
##      If check one by one, it would be O(n*w)
##
##      We can build a set from wordList, then it change 1 characters to all possible combinations
##      The complexity would be O(26*w) = O(w)
##
## Complexity: Time O(?), Space O(n*w)
##          n = len(wordList), w=len(word)
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        queue, wordSet = [], set(wordList)
        self.findNeighbors(beginWord, wordSet, queue):

        level = 2
        while len(queue) != 0:
            for i in xrange(len(queue)):
                word = queue[0]
                if word == endWord: return level
                del queue[0]
                # find the next candidates
                for w in self.findNeighbors(word, wordSet, queue):
                    queue.append(w)
            level += 1
        return 0

    def findNeighbors(self, word, wordSet, queue):
        for i in xrange(len(word)):
            for ascii in range(ord('a'), ord('z')+1):
                ch = chr(ascii)
                # skip itself
                if ch == word[i]: continue
                newWord = word[:i] + ch+ word[i+1:]
                # Only if it's unchecked and valid
                if newWord in wordSet:
                    queue.append(newWord)
                    wordSet.remove(newWord)

Post Views: 5