如何修改现有Python代码从单词集合中查找最长首尾循环的单词序列

修改思路 #

我们仅需要调整原有两个函数的逻辑，增加闭环校验规则即可实现需求：

1. 给longest_path_from新增参数记录起点单词的首字母，在路径遍历到终点（无可用邻居）时，校验当前单词的尾字母是否等于起点首字母，只有符合条件的路径才作为有效路径返回
2. 调整longest_path遍历逻辑，每个单词作为起点时传入对应首字母参数，最终从所有合法循环路径中取最长值

完整修改后代码 #

def get_neighbors(word, choices):
    return set(x for x in choices if x[0] == word[-1])


def longest_path_from(word, choices, start_first_char):
    choices = choices - {word}
    neighbors = get_neighbors(word, choices)

    max_path = []
    if neighbors:
        # 遍历所有邻居的有效路径取最长
        for w in neighbors:
            sub_path = longest_path_from(w, choices, start_first_char)
            if len(sub_path) > len(max_path):
                max_path = sub_path
    
    if max_path:
        # 有有效子路径，拼接当前单词返回
        return [word] + max_path
    else:
        # 无有效子路径，校验当前是否能单独构成闭环终点
        return [word] if word[-1] == start_first_char else []


def longest_path(choices):
    valid_cycles = []
    for w in choices:
        cycle = longest_path_from(w, choices, w[0])
        if cycle:
            valid_cycles.append(cycle)
    # 没有有效循环返回空列表，有则返回最长的
    return max(valid_cycles, key=len) if valid_cycles else []

效果测试 #

运行你给出的示例：

print(longest_path({'ca', 'abc', 'cd', 'da'}))

会输出长度为3的合法循环序列，如['abc', 'cd', 'da']，和预期结果一致。
注：如果存在多个相同长度的合法循环序列，返回结果可能为其中任意一种（循环序列本身支持旋转，均符合约束要求）。

内容的提问来源于stack exchange，提问作者user1361879