127.World-Ladder.md

127. World Ladder

Difficulty: Medium

URL

https://leetcode.com/problems/word-ladder/

Solution

Approach 1: BFS

This is the most intuitive idea in my opinion, in order to check the shortest transformation. We do breadth first search on the whole word list and let the search depth represent how many steps we've gone so far. Intuitively, we begin with the beginWord and scan through the wordList, check whether the current word has only one different character with the word we are examining, if it is, then this word is the desired neighbour and we should add it to our search queue. Once we reach the endWord in the wordList, it should signal the end of searching.

One drawback of this BFS strategy is that each time we scan through the whole list, which requirs $O(n)$ time for each pass of searching. Thus the naive BFS will result in $O(n^3)$ overall runtime and $O(n)$ space.

I use hash set data structure, which is implemented with red-black tree to boost the runtime. The idea is also really simple, once we a neighbour word and add it to our search queue, we never care about it in the later process, in other words, we should only record the neighbour word the first time we meet it. Thus, we can use a set data structure to keep track of this information, once we add a neighbour word to our search queue, then we remove it from the set. Next time we only examine the remaining words in the set. The runtime for this method is difficult to analysis, the rough upper bound is probably $O(n^2)$.

The code is shown below:

// Word Ladder
// 25.66% time, 97.73% space
// Accepted

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        vector<string>::iterator it;
        // Extrema case
        for (it=wordList.begin(); it!=wordList.end(); it++)
            if (*it==endWord)
                break;
        if (it==wordList.end()) // the case that the wordList doesn't contain the endWord
            return 0;
        
        // Based on the requirement which is "shortest". BFS seems to be a good choice
        queue<string> q;
        unordered_set<string> hashset(wordList.begin(), wordList.end());
        int step = 0;
        int listSize = wordList.size();
        q.push(beginWord);
        while (!q.empty()) {
            step += 1;
            if (step > listSize+1)
                return 0;
            int size = q.size();
            for (int i=0; i<size; i++) {
                string s = q.front();
                if (s == endWord)
                    return step;
                // on this step, we need to boost enqueue from O(n^2) to O(n)
                for (unordered_set<string>::iterator iter=hashset.begin(); iter!=hashset.end();) {
                    if (stringCompare(*iter, s)) {
                        q.push(*iter);
                        hashset.erase(iter++);
                    }
                    else
                        ++iter;
                }
                q.pop();
            }
        }
        
        return 0;
    }

    bool stringCompare(string s1, string s2) {
        // return true if these is only one different character
        int count = 0;
        for (int i=0; i<s1.length(); i++)
            if (s1[i] != s2[i])
                count++;
        
        return count == 1;
    }
};


int main() {
    Solution test;
    string beginWord = "hog";
    string endWord = "cog";
    vector<string> wordList = {"cog"};
    // vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    // vector<string> wordList = {"hot", "dot", "dog", "lot", "log"};
    // vector<string> wordList = {"a", "b", "c"};
    int res = test.ladderLength(beginWord, endWord, wordList);
    cout << res << endl;

    return 0;
}

Approach 2

from collections import Counter
from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:        
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        q = deque([beginWord])
        step = 0
        wordList.discard(beginWord)
        while len(q) != 0:
            sz = len(q)
            step += 1
            for _ in range(sz):
                cur_node = q.popleft()
                if cur_node == endWord:
                    return step
                for i in range(len(cur_node)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        next_node = cur_node[:i] + c + cur_node[i+1:]
                        if next_node in wordList:
                            wordList.remove(next_node)
                            q.append(next_node)
        return 0