在给定列表中一次搜索一个字符将一个字符串转换为另一个字符串的最短方法

Question

给定 list 个具有 SAME 长度的字符串，寻找将 start 字符串转换为 end 字符串的方法一次一个字符，这样每个转换后的字符串仍然存在于 list 个字符串中。

输入！
输入以 T 开头的测试用例数。然后，在另一行中出现 m 询问要放入列表中的字符串数。 m 行要求相同长度的字符串，最后一行由 start 和 end 组成，由 space.

分隔

示例：

List: ["booster", "rooster", "roaster", "coaster", "coasted"] 
start: roaster
end: booster

Number of String Transformation: 3 (roaster -> rooster -> booster)


List: ["booster", "rooster", "roaster", "coaster", "coasted"] 
start: booster
end: coasted

Number of String Transformation: 3 (booster -> rooster -> roaster -> coaster -> coasted)


List: ["booster", "rooster", "roaster", "coaster", "coasted", "coastal"] 
start: roaster
end: coastal

Number of String Transformation: impossible (roaster -> coaster -> coasted -> x -> coastal)

没有可能的方法就输出impossible。否则，输出最短的方式进行变换。

我采用了递归方法，但这无法找到所有可能的解决方案，因为它只尝试更改不等于 end 字符串的索引，它会跳过 list 中存在的一些字符串这可能会导致一个可能的解决方案。

我的代码适用于第一个示例但错过了第二个示例，因为它没有尝试 (booster -> rooster -> etc...) 因为它只将 (booster -> cooster -> coaster -> coasted) 视为可能的解决方案。我有点卡住了，我不知道如何解决这个问题。有人可以告诉我更好的方法吗？

def transformable(word_1, word_2):
    return len([i for i in range(len(word_1)) if word_1[i] != word_2[i]]) == 1

def shortest_transformation(start, end, words):
    queue = [[start]]
    available = set(words).difference({start})
    while queue:
        path = queue.pop()
        if transformable(path[-1], end):
            return path + [end]
        transformables = set(word for word in available if transformable(path[-1], word))
        queue = [path + [word] for word in transformables] + queue
        available = available.difference(transformables)
    return None

T = int(input())

for case in range(T):
    m = int(input())
    words = []
    for inputs in range(m):
        words.append(input())
    
    start, end = input().split()
    
    result = shortest_transformation(start, end, words)
    print(len(result)) if result else print("none")

4
5
booster
rooster
roaster
coaster
coastal
booster coastal
6
booster
rooster
roaster
coaster
coasted
coastal
booster coastal
5
booster
rooster
roaster
coaster
coasted
booster coasted
5
booster
rooster
roaster
coaster
coasted
roaster booster

Output:
none
none
5
3

Answer 1

如果您还没有找到解决方案，这里有一个建议：

from collections import deque

def transformable(word_1, word_2):
    return len([i for i in range(len(word_1)) if word_1[i] != word_2[i]]) == 1

def shortest_transformation(start, end, words):
    queue = deque([[start]])
    words = set(words).difference({start})
    while queue:
        path = queue.pop()
        if transformable(path[-1], end):
            return path + [end]
        transformables = set(word for word in words if transformable(path[-1], word))
        queue.extendleft(path + [word] for word in transformables)
        words = words.difference(transformables)
    return []

这是一种广度优先搜索（通过使用 deque 的 .extendleft() 方法的 LILO/FIFO 队列），这是一种搜索最短路线的好方法。

举个例子

words = ["booster", "rooster", "roaster", "coaster", "coasted"] 
start = 'roaster'
end = 'booster'
print(shortest_transformation(start, end, words))

words = ["booster", "rooster", "roaster", "coaster", "coasted"] 
start = 'booster'
end = 'coasted'
print(shortest_transformation(start, end, words))

words = ["booster", "rooster", "roaster", "coaster", "coasted", "coastal"] 
start = 'roaster'
end = 'coastal'
print(shortest_transformation(start, end, words))

输出是

['roaster', 'rooster', 'booster']
['booster', 'rooster', 'roaster', 'coaster', 'coasted']
[]

如果您不想使用 deque 那么这应该是等效的：

def shortest_transformation(start, end, words):
    queue = [[start]]
    available = set(words).difference({start})
    while queue:
        path = queue.pop()
        if transformable(path[-1], end):
            return path + [end]
        transformables = set(word for word in available if transformable(path[-1], word))
        queue = [path + [word] for word in transformables] + queue
        available = available.difference(transformables)
    return None

在给定列表中一次搜索一个字符将一个字符串转换为另一个字符串的最短方法

Search for the shortest way to turn a string to another string one character at a time in a given list

python

recursion

search

list

divide-and-conquer