Python中的单词阶梯问题

2025年1月5日 | 阅读 7 分钟

假设我们有一个字典。此外，我们还有两个单词；让这两个单词是A和B。在这个问题中，我们必须找到从A到B的最小链，如果存在，则返回这个最小链的长度。链应该这样形成：链中的相邻项，例如，在链A Þ C Þ B中，单词A和C是相邻的，并且它们的差异不超过一个字符。我们还必须确保链中的每个单词都必须是有效的单词。通过检查单词是否存在于字典中，我们可以确保单词是否有效。我们可以假设单词B存在于字典中，并且每个单词的长度都相同。

让我们看一些例子来理解这个问题。

输入：字典 = ["hot", "dot", "dog", "lot", "log", "cog"]，开始 = "hit"，目标 = "cog"

输出 5

方法 - 1

在第一种方法中，我们将使用广度优先搜索算法来解决这个问题。我们在BFS算法中使用队列数据结构。因此，我们将从起始单词开始，并将该单词推入队列以初始化队列。我们将使用BFS算法遍历字典，直到返回BFS的当前级别，这将是链的长度。在BFS的每个级别，我们都可以访问当前单词可以转换到的所有单词。因此，当我们遇到目标元素时，它将是通过最短的链。

让我们看看该方法的算法：

我们将初始化一个队列并将起始单词传递给它。
然后，我们将启动一个while循环，该循环将一直运行，直到队列中有元素或我们尚未遇到目标单词。
我们将遍历当前单词的每个相邻单词，并将这些相邻单词推入我们的队列。
我们将继续此过程，直到队列不为空或我们已到达目标单词。
如果循环在未中断的情况下结束，则意味着我们无法使用起始单词到达目标单词；因此，我们将返回False。

让我们看看Python代码。

代码

# Python program to show how to find the length of the shortest chain to reach to the target word from the given start word using BFS

# Defining a function that will take the dictionary, the start word and the target word. It will return the length of the shortest chain if a chain is possible, or it will return False if the chain cannot be formed.
def shortestChain(start, target, dic):
  
  # If the start and the target words are the same, we do not need to traverse the dictionary
  if start == target:
   return 0

  # If the given target word is not a member of the dictionary, then the chain cannot be formed; hence, we will return False
  if target not in dic:
    return False

  # Initializing the variables to store the length of the chain and the length of the word
  l, wordlen = 0, len(start)

  # Initializing a queue for the BFS traversal and passing the start word to the queue
  Q = [start]

  # Starting the while loop for the BFS traversal
  while (len(Q) > 0):
     
    # For each iteration, incrementing the level and hence the length of the chain
    l += 1

    # Storing the length of the current queue
    size = len(Q)

    # Since, alongside traversing the queue, we are adding elements to the queue, we will iterate over the range of the length of the current queue.
    # In this way, we will not start iterating over the elements of the next level.
    # This for loop will complete once all the elements of the current level are traversed
    for i in range(size):

      # Removing the 0th word from the current queue
      word = [j for j in Q.pop(0)]

      # We will find all the adjacent words of the current word
      for i in range(wordlen):
         
        # Retaining the original letter at the current position
        orig = word[i]

        # Trying each word by replacing the current letter with every possible English letter
        for letter in range(ord('a'), ord('z')+1):
          word[i] = chr(letter)

          #If the new word after replacement is the same as the target word, then we will return the current level
          if ("".join( word ) == target):
            return l + 1

          # Removing the current word from the set if the word is not found in the dictionary
          if ("".join( word ) not in dic):
            continue
             
          del dic["".join( word )]

          # We will push the new word into the queue
          Q.append("".join( word ))

        #Restoring the original word by replacing the changed letter with the original letter
        word[i] = orig

  # If the program has reached this point, that means the chain is not possible; hence, we will return a False
  return False
   
# Make dictionary
D = {}
D["hot"] = 1
D["dot"] = 1
D["dog"] = 1
D["lot"] = 1
D["log"] = 1
D["cog"] = 1
start = "hit"
target = "cog"
ans = shortestChain(start, target, D)
if ans != False:
  print("The length of the shortest possible chain is: ", ans)
else:
  print("A chain is not possible")

输出

The length of the shortest possible chain is: 5

时间复杂度：对于BFS，我们正在对字典执行嵌套循环。因此，此循环的时间复杂度是非线性的。因此，它是O(N2)，其中N是字典的长度。对于这个嵌套循环，我们正在迭代单词的字符；因此，除了N2之外，还有单词长度的一个或多个分量。因此，最终时间复杂度为O(N² * M)，其中M是字符串的长度。

空间复杂度：此方法空间复杂度为O(M * N)

方法 - 2

在此方法中，我们将创建从我们开始时的原始单词到所有中间单词之间的映射。

让我们看看这种方法是如何工作的。在此方法中，我们将首先找到给定起始单词与字典中存在的单词之间的中间单词。我们将创建一个中间单词与包含原始单词字符的列表之间的映射。例如，如果我们有单词“Hot”，该单词的中间单词是“*ot”、“H*t”和“Ho*”。然后，我们将以起始单词作为起始单词执行BFS遍历。在BFS遍历的队列中，我们将添加起始单词和距离起始单词的距离对。这样，最后，距离就是我们的答案。

代码

# Python program to find the shortest chain between the target word and the start word

# Importing the required libraries
from typing import List, Tuple, Set, Dict, Any, Union

# Defining a function that takes the start and target word and a set of words and returns the length of the shortest chain
def shortestChain(start, target, dic):

  # If the start and the target words are the same, we do not need to traverse the dictionary
  if start == target:
   return False

  # Creating a map between the intermediate words and the vector of the string of the original word
  map = {}

  # Initializing the map by adding the intermediate words of the start word
  for s in range(len(start)):

    # Creating an intermediate word for the original word
    intermediate = start[ : s] + "*" + start[s + 1 : ]

    # Adding the word to the dictionary
    map[intermediate] = []

  # We will find all of the intermediate words for all of the words given in the dictionary
  for word in dic:
    for i in range(len(word)):

      # Creating an intermediate word for the current word
      intermediate = word[ : i] + "*" + word[i + 1 : ]

      # Checking if the current intermediate word is already on the map
      if intermediate not in map:
        # If the word is not on the map, then we will add that word to the map
        map[intermediate] = []
      # If the current intermediate word is in the map, then we will add the original word to the mapping vector of the current intermediate word
      map[intermediate].append(word)

  # Performing the BFS traversal

  # Initializing the queue and adding the start word and distance to the queue
  q = [(start, 1)]

  # Creating a dictionary to mark the visited words
  visited = {start: 1}

  # Traversing until the BFS traversal queue is empty
  while q:
    w, d = q.pop(0)

    # Checking if we have reached the target words
    if w == target:
      return d

    # Finding the intermediate word of the current word and storing the vector of mapped words
    for i in range(len(word)):
      intermediate = w[ : i] + '*' + w[i + 1 : ]
      v = map[intermediate]
      for k in range(len(v)):
        
        # Checking if the current word is visited or not
        if v[k] not in visited:
          visited[v[k]] = 1
          q.append((v[k], d + 1))

  # If we cannot reach the target word, we will return a False
  return False

# Make dictionary
D = {}
D["hot"] = 1
D["dot"] = 1
D["dog"] = 1
D["lot"] = 1
D["log"] = 1
D["cog"] = 1
start = "hit"
target = "cog"
ans = shortestChain(start, target, D)
if ans != False:
  print("The length of the shortest possible chain is: ", ans)
else:
 print("A chain is not possible")

输出

The length of the shortest possible chain is: 5

时间复杂度：在此方法中，我们运行一个嵌套循环，因此时间复杂度将是非线性的。此外，我们正在迭代单词的字符；因此，最终时间复杂度将为O(N² * M)，其中N是字典的长度，M是字符串的长度。

空间复杂度：此方法也使用O(M * N)的空间复杂度，因为我们使用此空间来存储单词并创建映射。

下一个主题Attribute-list-in-python

Python中的单词阶梯问题

方法 - 1

方法 - 2

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中的单词阶梯问题

方法 - 1

方法 - 2

相关帖子

Python中的os.system()方法

Python中的First Fit算法

Python math.cmp方法

使用Python Requests发送表单数据

Python程序：查找两个列表的笛卡尔积

Python中的from...import语句的用途是什么

Python - 哈希表

理解TF-IDF（词频-逆文档频率）使用Python

使用Python和Rasa构建聊天机器人

Python中的CDF图

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器