Leetcode - Word Ladder

Leetcode : Word Ladder

Description

Given two words beginWord and endWord, and a dictionary wordList, return the length of the 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.
• Return 0 if there is no such transformation sequence.

Example 1

Input

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output

5

# 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

Approach

BFS-algorithm is required to solve this problem since we are to return the shortest transformation sequence from beginWord to endWord. However, this problem is not just about BFS but also about pre-processing inputs by brute-forcing every possible options which match the pair in wordList.

Solution (Python)

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0 

        qu = [(beginWord, 1)]
        size = len(beginWord)
        visit = {}
        permute = {}

        for word in wordList:
            visit[word] = False

        for word in wordList:
            for i in range(size):
                op = word[:i] + '*' + word[i+1:]

                if op not in permute:
                    permute[op] = [word]
                else:
                    permute[op].append(word)

        while qu:
            cur, cnt = qu.pop()

            visit[cur] = True

            if cur == endWord:
                return cnt 

            for i in range(size):
                op = cur[:i] + '*' + cur[i+1:]

                if op not in permute:
                    permute[op] = []
                else:
                    for poss in permute[op]:
                        if visit[poss] == False:
                            qu.insert(0, [poss, cnt+1])
        return 0 

Result

Runtime : 3196ms
Memory Usage : 20.5MB
Runtime Beats 6.53% of Python Submission