在给定起点和终点的字符串列表中检查路径

Question

我们的任务是创建一个程序，在给定具有相同的字符串列表的情况下，检查是否存在从起始字符串到结束字符串的可能方法长度。有一个问题，如果两个字符串只有一个不同的字符，我们只能从当前字符串转到相邻字符串。如果从起始字符串到结束字符串没有可能的路径，则打印 not possible 但如果存在，则输出从开始到结束的步数。

Example:
li = ["booster", "rooster", "roaster", "coaster", "coasted"]
start = "roaster"
end = "booster"

Output: 3

li = ["booster", "rooster", "roaster", "coastal", "coasted"]
start = "roaster"
end = "coasted"

Output: none

我采用了一种方法，手动检查相邻字符串是否只有 1 个字符差异，returns 根据这些差异得出结果。考虑到列表的长度最多 100，如果你问我的话有点慢。您能展示一种更快的方法吗？

def checker(str1, str2, change = 0):

    for index, character in enumerate(str1):      # Traverses the whole
        if character != str2[index]:              # string and checks for   
            change+=1                             # character differences 
                                                  

    return True if change == 1 else False              # Only 1 character is different

li = ["booster", "rooster", "roaster", "coaster", "coasted"]
m = len(li)

for j in range(m): li.append(input())
start, end = input().split()

if end in li: endI = li.index(end)               # Gets end string index in the list
else:
    print("not possible")
    break

if start in li: startI = li.index(start)         # Gets start string index in the list
else:
    print("not possible")
    break

if startI < endI:                                # If start string comes first before 
                                                 # the end string, keep incrementing.

    while li[startI] != end and startI < m-1:

        if not checker(li[startI], li[startI+1]):
            print("not possible")
            break

        startI += 1

    print(abs(startI-(li.index(start)+1)))

else:                                            # Otherwise, keep decrementing.                                             

    while li[startI] != end and startI > 0:

        if not checker(li[startI], li[startI-1]):
            print("not possible")
            break

        startI -= 1

    print(abs(startI-(li.index(start)+1)))

如果我的方法是最快的（对此我深表怀疑），我想知道我的方法是否存在漏洞。假设给定的列表中也可以不存在开始和结束字符串。如果他们不在列表中，只需打印 not possible。

Answer 1

我希望看起来更好：

import regex

def word_path(words, start, end):
    if end in words and start in words:
        endI = words.index(end)
        startI = words.index(start)
    else:
        return "not possible"

    step = 1 if startI <= endI else -1

    for index in range(startI, endI, step):
        if not regex.match("(%s){e<=1}" %li[index], li[index + step]):
            return "not possible"
    return abs(startI - endI) + 1

li = ["booster", "rooster", "roaster", "coastal", "coasted"]
start, end = input().split()
print(word_path(li, start, end))

Answer 2

应该是正则表达式。 Regex 提供额外的正则表达式功能，例如它可以检查一些错误 {e<=1}。 re- 模块不提供这些功能。我想这就是错误结果的原因。您可能需要先使用 pip install regex 安装 regex-module，但它应该可以工作：

regex_module

在给定起点和终点的字符串列表中检查路径

Checks for a Path in a List of Strings Given a Starting and Ending Point

python

string

search

path

divide-and-conquer