字符串转换

Question

我遇到了以下 article这让我对这个特殊问题产生了兴趣。

Given two words "CAT", "FAR" determine if you can get from the first to the second via single transformations of valid words....e.g. 1 transformation gets you from CAT to CAR changing T to R, then another gets you from CAR to FAR changing the C to F...all are valid english words.

有什么想法吗？不太确定如何开始说实话。如果你给我指出正确的方向，那就足够了。谢谢!

Answer 1

如 this answer 中所述(谢谢，aix)，这是一个最短路径问题，可以用 A* algorithm 有效地解决使用 Hamming distance (即两个单词不同的字母数)作为启发式。