详尽地获得三个字母的所有可能组合

Question

我正在研究leetcode问题“ wordLadder”

给定两个单词（beginWord和endWord），以及字典的单词列表，找到从beginWord到endWord的最短转换序列的长度，例如：

1. 一次只能更改一个字母。
2. 每个转换的单词都必须存在于单词列表中。需要注意的是beginWord是不是变换词。

注意：

• 如果没有这样的转换序列，则返回0。
• 所有单词的长度相同。
• 所有单词仅包含小写字母字符。
• 您可以假设单词列表中没有重复项。
• 您可以假设beginWord和endWord为非空并且不相同。

范例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.

范例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.

我的解决方案

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        visited = set()
        wordSet = set(wordList)

        queue = [(beginWord, 1)]

        while len(queue) > 0:
            word, step = queue.pop(0)
            logging.debug(f"word: {word}, step:{step}")

            #base case 
            if word == endWord:
                return step #get the result.
            if word in visited: #better than multiple conditions later.
                continue

            for i in range(len(word)):
                for j in range(0, 26): 
                    ordinal = ord('a') + j
                    next_word = word[0:i] + chr(ordinal) + word[i + 1:]
                    logging.debug(f"changed_word: {next_word}")
                    if next_word in wordSet: 
                        queue.append((next_word, step + 1))
            visited.add(word) # paint word as visited

        return 0 

用尽所有可能的单词组合

我阅读了讨论区，全部采用了切片技术

next_word = word[0:i] + chr(ordinal) + word[i + 1:]

还有其他解决方案可以解决该问题吗？

Answer 1

这是一个经典的网络问题。您应该做的是生成一个方阵，其尺寸等于字典中的单词数。然后用 1 填充矩阵，只要单词之间是一个字母的转换，即

network['hot']['not'] = 1

所有其他单元格都需要0。

现在你定义了你的网络，你可以使用像 Dijkstra 这样的最短路径算法来解决你的问题