换字器可达性

Question

改变词是一种游戏，你试图通过单一字符编辑把一个词变成另一个字，每一步都是它自己的词。对于此挑战，编辑可以是替换、插入或删除。例如，胜利者→输家可以使用此路径(可能还有其他)：

WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

另一种说法是，你必须能够从另一个单词到达另一个单词，每次只有1的Levenshtein距离。

编码

您将获得一个单词列表和两个单词，如果存在路由，则必须输出一个从一个字到另一个字的有效路由，如果不存在路由，则必须输出一个不同的常量值或一致行为。

• 您可以假设输入的单词都在单词列表中。
• 单词列表可以通过任何方便的平面格式获取。
  • 列表、集合、尝试、空格分隔的字符串和分隔行的文件都是有效的(例如)，但是一个预先计算的Levenshtein邻接图不是。

• 输出路径应该包括两个输入单词，但什么开始和结束并不重要。
• 如果找不到路径，则可以输出特定的常量、虚值、空列表、抛出异常、使用非零代码退出或在有限时间内发生的任何其他行为。
• 路线不需要是最优的，也不需要选择哪一条路线。
• 计算复杂性并不重要，但是您的程序必须保证在有限的时间内终止。(即使它会超越宇宙的热死)
• 你可以假设所有的单词都是在同一情况下由字母组成的。

示例测试用例

• 猫猫，狗，COG，婴儿床，青蛙，沼泽地，沼泽 →狗
  • 猫，婴儿床，COG，狗

• 洗澡，淋浴，有，帽子，蝙蝠，SAT，锯，播种，展示，如何 浴缸→淋浴
  • 找不到路线

• 破坏打破，固定，喙，面包，阅读，珠，红色，床，坏，出价，时尚，传真 ；→修复
  • 打破，面包，珠子，坏，时尚，传真，修理

• 构建建造，摧毁，建造，内疚，行会，镀金，鳃，比尔，迪尔，填充，破坏，结构，建筑 ；→破坏
  • 找不到路线

• 卡片，板子，巴德 卡→板
  • 卡片，吟游诗人，董事会

• 恶魔恶魔，天使 →天使
  • 找不到路线

• 最后一次过去；最后，过去，爆炸，铸造，黑色，幽灵，张贴，吹嘘
  • 最后，过去

• 插入这个单词列表 ；→删除
  • 插入、倒置、发明、内弯、不弯曲、不弯曲、不绑定、不友好、不加修饰、发条、发怒、发条、黑暗、亲爱的、箭、病、亲、丝、丝、神经、NERITE、CERITE、CERATE、DERATE、DELATE、删除

Answer 1

Wolfram语言(数学)，59字节

Select[Rule@@@#~Tuples~2,EditDistance@@#<2&]~FindPath~##2&;

在网上试试！

Answer 2

Python 2，155个字节

f=lambda a,b,W,r=[]:a==b and r+[a]or reduce(lambda q,w:q or any({a,a[:i]+a[i+1:]}&{w,w[:i]+w[i+1:]}for i in range(len(a+w)))and f(w,b,W-{a},r+[a]),W-{a},0)

在网上试试！

将两个单词和一组单词作为输入；如果以字符串列表的形式存在，则返回(非最佳)路由，否则返回False。

这一片段：

any({a,a[:i]+a[i+1:]}&{w,w[:i]+w[i+1:]}for i in range(len(a+w)))

是True当且仅当a==w或a有1与w之间的Levenshtein距离。

Answer 3

Wolfram语言(数学)，124个字节

Join[#,Select[Flatten[Permutations/@Subsets@#3,1],s=#;t=#2;Union[EditDistance@@@Partition[Join[s,#,t],2,1]]=={1}&][[1]],#2]&

在网上试试！