LeetCode | 0127. Word Ladder単語ドラゴン【Python】

LeetCode 0127. Word Ladder単語ドラゴン【Medium】【Python】【BFS】
Problem
LeetCode
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of 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. Note that beginWord is not a transformed word.

Note:

Return 0 if there is no such transformation sequence.

All words have the same length.

All words contain only lowercase alphabetic characters.

You may assume no duplicates in the word list.

You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output: 5

Explanation: 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

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

に質問
スナップ
2つの単語(beginWordとendWord)と辞書を指定し、beginWordからendWordへの最短変換シーケンスの長さを見つけます.変換には、次のルールが必要です.

変換するたびに1文字しか変更できません.

変換中の中間単語は、辞書の単語でなければなりません.

説明:

このような変換シーケンスが存在しない場合、0が返される.

すべての単語は同じ長さを有する.

すべての単語は小文字のみで構成されています.

辞書に重複する単語は存在しません.

beginWordとendWordは空ではなく、両者が異なると仮定できます.

例1:

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

  : 5

  :           "hit" -> "hot" -> "dot" -> "dog" -> "cog",
            5。

例2:

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

  : 0

  : endWord "cog"      ，        。

構想
解法一
BFS

                       ，           。
                   ，    BFS。
  26       26    。

Python 3コード

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # solution one: BFS
        wordDict = set(wordList)  # no duplicates in the word list
        if endWord not in wordDict:
            return 0
        
        q, visited = [(beginWord, 1)], set()
        while q:
            word, step = q.pop(0)
            if word not in visited:
                visited.add(word)
                if word == endWord:
                    return step
                for i in range(len(word)):
                    for j in "abcdefghijklmnopqrstuvwxyz":  # 26 directions
                        temp = word[:i] + j + word[i+1:]
                        if temp in wordDict and temp not in visited:  # different ways from beginWord to endWord
                            q.append((temp, step + 1))
        return 0

解法二
双方向BFS

start: hit
end: cog
wordDict: hot dot dog lot log 
stack:

  ，start    ，         temp     wordDict  ，         ，          end  ，       step + 1，       temp     stack  。

start: hit
end: cog
wordDict: hot dot dog lot log 
stack: hot

     len(stack) < len(end)，      start     stack，       start     end     end     stack，    step + 1。

start: cog
end: hot
wordDict: hot dot dog lot log 
stack: hot

        cog->hot      ，         。         start   end    ，       0         。

Python 3コード

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # solution two: Double BFS
        wordDict, step = set(wordList), 1
        if endWord not in wordDict:
            return 0
        start, end = set([beginWord]), set([endWord])
        while start:
            stack = set([])
            wordDict -= start

            for s in start:
                for i in range(len(beginWord)):
                    for j in string.ascii_lowercase:  # a-z
                        temp = s[:i] + j + s[i+1:]
                        if temp not in wordDict:
                            continue
                        if temp in end:
                            return step + 1
                        stack.add(temp)
            if len(stack) < len(end):
                start = stack
            else:
                start, end = end, stack
            step += 1
        return 0

コードアドレス
GitHubリンク
リファレンス
Leetcode 127:単語の受け渡し(最も詳しい解法!!)