Hex.*

LC127 - Word Ladder

Posted on In
Leetcode: 153/2658 (59+74+20)

Description

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.

Example 2:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.

Solution

  • Think of words as nodes, and bring out the adjacent nodes of the next layer from one node, and use BFS to do it.
  • Maintain a queue, let the starting word enter the queue, the level is 1, and then dequeue it for investigation.
  • Turn each character into one of the 26 letters to see if it is in the word list, if so, the new word is the conversion word for the next level.
  • enqueue it, its level +1, and delete the word from the word list.
  • Dequeue, enqueue… Repeat, when the dequeued word is the same as the end word, the end word is encountered, and its level is returned.
  • When the queue is empty, it means that all words have been examined, no end word has been encountered, and there is no path leading to the end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# O(N×C^2) time | O(N×C^2) space
from collections import deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        n = len(endWord)
        queue = deque([(beginWord,1)])
        while queue:
            word, step = queue.popleft()
            if word == endWord:
                return step
            
            for w in range(len(word)):
                for i in range(ord('a'), ord('z')+1):
                    temp = word[:w] + chr(i) + word[w+1:]
                    if temp in wordSet:
                        queue.append((temp, step+1))
                        wordSet.remove(temp)
        return 0