127. Word Ladder - cocoder39/coco39_LC GitHub Wiki

127. Word Ladder

M words and each word of length N then time complexity is M * N * 26 * N

To get the next word, this approach update each char in the original word from a to z, time complexity is N * 26 * N. An alternative approach is to compare each pair within the input, the time complexity of getting the next word is M * N

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if not beginWord or not endWord or not wordList:
            return 0
                
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0
        
        queue = collections.deque([(beginWord, 1)])
        visited = set([beginWord])
        while queue:
            word, level = queue.popleft()
            if word == endWord:
                return level
            
            for i in range(len(word)):
                for j in range(ord('a'), ord('z')+1):
                    ch = chr(j)
                    new_word = word[:i] + ch + word[i+1:]
                    #print(new_word)
                    if new_word not in visited and new_word in wordSet:
                        visited.add(new_word)
                        queue.append([new_word, level+1])
        return 0

================================================================================

framework of BFS: use queue to do level by level bfs

while (! q.empty()) {
  int sz = q.size();
  for (int i = 0; i < sz; i++) {
    q.front();
    q.pop();
    ...
  }
}

time complexity of finding shortest path in unweighted graph using bfs is O(V + E). Here E is replaced by V * 26 * len where len is length of a word. Thus time is O(V + V * 26 * len) = O(V * len)

one tip is erasing node that has been visited.

int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        if (beginWord == endWord) {
            return 1;
        }

        int dist = 1;
        queue<string> q;
        q.push(beginWord);
        if (wordList.find(beginWord) != wordList.end()) {
            wordList.erase(beginWord);
        }
        
        while (! q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                string word = q.front();
                q.pop();
                for (int j = 0; j < word.length(); j++) {
                    char backup = word[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        word[j] = c;
                        if (word == endWord) {
                            return dist + 1;
                        } else if (wordList.find(word) != wordList.end()) {
                            wordList.erase(word);
                            q.push(word);
                        }
                    }
                    word[j] = backup;
                }
            }
            dist++;
        }
        return 0;
    }
⚠️ **GitHub.com Fallback** ⚠️