Leetcode - Word Ladder

Ji Kim·2021년 1월 11일
0

Algorithm

목록 보기
32/34

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

profile
if this then that

0개의 댓글