127. Word Ladder

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

Thoughts:

1. BFS: Generate the qualified permutation, add distance by 1, until find the answer or queue is empty

2. Optimizations:

   1. Python:

      1. 1. Character flopping: flop (expanding the transformation candidate in the "front" set, then check whether it is in the word dictionary: T: O(M*26*L*L); O(L) . M: Dictionary Size, L: word length,

      2. 1. Dictionary Checking: Checking whether a word in current wordDictionary can be transformed into current word in the set: T:O(MNL). N: number of words in the dictionary.

      3. Removing entries in S from T vs Creating new entries from S if it is not in T.

   2. C++

Code

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        def generateNeighbors(word, wordList):
            for i in range(len(word)):
                for letter in string.ascii_lowercase:
                    candidate = word[:i] + letter + word[i+1:]
                    if candidate in wordList:
                        yield candidate
        # We use q to keep track of the next nodes to process in the BFS.
        # Each item in the queue is a list with two items:
        #   item[0] = word
        #   item[1] = steps to reach word + 1 (i.e. number of nodes in list of nodes 
        #             traversed to reach word - (format of Word Ladder I output)).
        q = collections.deque([ [beginWord,1] ])
        # We keep track of words we've processed to avoid getting stuck in a loop.
        seen = set([beginWord])
        # wordList is given as a list but we want O(1) lookup so we convert to a set.
        wordList = set(wordList)
        while q:
            q_item = q.popleft()
            for candidate in generateNeighbors(q_item[0], wordList):
                if candidate == endWord:
                    return q_item[1] + 1
                elif candidate in seen:
                    continue
                seen.add(candidate)
                q.append([candidate, q_item[1] + 1])
        return 0

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        dist = 2
        n = len(beginWord)
        wordDict = set(wordList)
        wordDict.discard(beginWord)

        # corner case: since we assume endWord is in wordDict when doing the swapping
        if endWord not in wordDict:
            return 0

        front, back = set([beginWord]), set([endWord])

        while front:
            # generate all valid permutations
            front = wordDict & set([word[:i] + c + word[i+1:]
                                    for word in front 
                                    for i in range(len(word))
                                    for c in string.ascii_lowercase
                                   ])

            if front & back:
                # there are common elements in front and back, done
                return dist

            dist += 1

            if len(front) > len(back):
                # swap front and back for better performance (fewer choices in generating nextSet)
                front, back = back, front 

            # remove transformations from wordDict to avoid cycle
            wordDict -= front


        return 0

Code: Python Optimization

class Solution:
    # @param {string} beginWord
    # @param {string} endWord
    # @param {set<string>} wordDict
    # @return {integer}
    def ladderLength(self, beginWord, endWord, wordDict):
        def generateNextSet1(current, wordDict, wordLen):
            nextSet = set()
            for word in current:
                for index in range(wordLen):
                    for ch in 'abcdefghijklmnopqrstuvwxyz':
                        nextWord = word[:index] + ch + word[index+1:]
                        if nextWord in wordDict:
                            nextSet.add(nextWord)
            return nextSet

        def generateNextSet2(current, wordDict):
            nextSet = set()
            for word in current:
                for nextWord in wordDict:
                    index = 0
                    try:
                        while word[index] == nextWord[index]:
                            index += 1
                        if word[index+1:] == nextWord[index+1:]:
                            nextSet.add(nextWord)
                    except:
                        continue
            return nextSet

        steps, wordLen = 2, len(beginWord)
        front, back = set([beginWord]), set([endWord])
        wordDict.discard(beginWord)
        switchThreshold = 26*wordLen
        while front:
            # get all valid transformations
            if len(wordDict) >= switchThreshold:
                front = generateNextSet1(front, wordDict, wordLen)
            else:
                front = generateNextSet2(front, wordDict)
            if front & back:
                # there are common elements in front and back, done
                return steps
            steps += 1
            if len(front) >= len(back):
                # swap front and back for better performance (smaller nextSet)
                front, back = back, front
            # remove transformations from wordDict to avoid cycles
            if (len(wordDict)>>1) >= len(front):
                # s.difference_update(t): O(len(t))
                wordDict -= front
            else:
                # s.difference(t): O(len(s))
                wordDict = wordDict - front
        return 0

Code: C++ OptimizationThe above code can still be speeded up if we also begin fromend. Once we meet the same word fromstartandend, we know we are done.This link provides a nice two-end search solution. I rewrite the code below for better readability. Note that the use of two pointerspheadandptailsave a lot of time. At each round of BFS, depending on the relative size ofheadandtail, we pointpheadto the smaller set to reduce the running time.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordDict (wordList.begin(), wordList.end());

        if (wordDict.find(endWord) == wordDict.end()) return 0;

        unordered_set<string> head, tail, *phead, *ptail;
        head.insert(beginWord);
        tail.insert(endWord);
        int dist = 2;
        while (!head.empty() && !tail.empty()) {
            if (head.size() <= tail.size()) {
                phead = &head;
                ptail = &tail;
            }
        else {
                phead = &tail;
                ptail = &head;
            }
        unordered_set<string> temp;
        for (auto itr = phead -> begin(); itr != phead -> end(); itr++) {
            string word = *itr;
            for (int p = 0; p < (int)word.length(); p++) {
                char letter = word[p];
                for (int k = 0; k < 26; k++) {
                    word[p] = 'a' + k;
                    if (ptail -> find(word) != ptail -> end())
                        return dist;
                    if (wordDict.find(word) != wordDict.end()) {
                        temp.insert(word);
                        wordDict.erase(word);
                        }
                    }
                word[p] = letter;
                }
            }

        dist++; 
        // throw away the expaned and add in new candidate into set
        *phead = temp;
        }

        return 0;
    }
};