对于数据结构项目，我必须找到两个单词（如"cat"和"dog"）之间的最短路径，一次只更改一个字母。我们得到了一个拼字游戏单词列表，用于寻找我们的路径。例如：
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题，但正在寻找更好的东西（我用特里树表示字典）。
请给我一些想法，以获得更有效的方法（在速度和内存方面）。一些荒谬和/或具有挑战性的东西是首选。
我问了我的一个朋友（他是一名大三学生），他说这个问题没有有效的解决方案。他说我会在学习算法课程时了解原因。对此有何评论？
我们必须逐字逐句。我们不能去cat -> dat -> dag -> dog。我们还必须打印出遍历。
新答案
鉴于最近的更新，您可以尝试使用汉明距离作为启发式的 A*。这是一种可接受的启发式方法，因为它不会高估距离
旧答案
您可以修改用于计算Levenshtein 距离的动态程序以获得操作序列。
编辑：如果有恒定数量的字符串，则问题可以在多项式时间内解决。否则，它是 NP 难的（维基百科中都有）.. 假设你的朋友正在谈论这个问题是 NP 难的。
编辑：如果您的字符串长度相等，则可以使用Hamming distance。
使用字典，BFS 是最佳的，但所需的运行时间与其大小（V+E）成正比。对于 n 个字母，字典可能有 ~a^n 个整数，其中 a 是字母大小。如果字典包含所有单词，但应该在链末尾的单词除外，那么您将遍历所有可能的单词但不会找到任何东西。这是图遍历，但大小可能呈指数级增长。
您可能想知道是否有可能更快地做到这一点——“智能地”浏览结构并在多项式时间内完成。答案是，我认为，不。
问题：
你有一个快速（线性）的方法来检查一个单词是否在字典中，两个单词 u, v 并检查是否有一个序列 u -> a 1 -> a 2 -> ... -> a n ->诉。
是 NP 难的。
证明：以一些 3SAT 实例为例，例如
(p or q or not r) and (p or not q or r)
您将从 0 000 00 开始，并检查是否可以转到 2 222 22。
第一个字符将是“我们完成了吗”，接下来的三个位将控制 p、q、r，而接下来的两个位将控制子句。
允许的词是：
要从 0 000 00 产生 2 222 22，您必须这样做：
(1) 翻转适当的位 - 例如分四步翻转 0 100 111。这需要找到 3SAT 解决方案。
(2) 将第一位更改为 2：2 100 111。在这里您将得到验证，这确实是一个 3SAT 解决方案。
(3) 改变 2 100 111 -> 2 200 111 -> 2 220 111 -> 2 222 111 -> 2 222 211 -> 2 222 221 -> 2 222 222。
这些规则强制您不能作弊（检查）。只有当公式是可满足的并且检查是 NP-hard 时，才可能转到 2 222 22。我觉得它可能更难（可能是#P 或 FNP），但我认为 NP 硬度足以达到这个目的。
编辑：您可能对不相交集数据结构感兴趣。这将获取您的字典和可以相互访问的组词。您还可以存储从每个顶点到根或其他顶点的路径。这会给你一条路径，不一定是最短的。
查找链接的效率有很多不同的方法——你可以为每个字长构建一个完整的图，或者你可以构建一个BK-Tree，例如，但你的朋友是对的——BFS 是最有效的算法。
但是，有一种方法可以显着改善运行时间：不要从源节点执行单个 BFS，而是执行两个广度优先搜索，从图的任一端开始，并在您在其边界集中找到公共节点时终止. 如果只从一端搜索，您需要做的工作量大约是所需工作量的一半。
首先，您可以通过删除长度不正确的单词来加快速度。更多有限的字典将适合 CPU 的缓存。大概都是。
此外，所有 strncmp 比较（假设您将所有内容都设为小写）都可以是 memcmp 比较，甚至是展开比较，这可以加快速度。
您可以使用一些预处理器魔术并针对该字长硬编译任务，或者针对常见字长滚动一些优化的任务变体。所有这些额外的比较都可以“消失”以获得纯粹的展开乐趣。
这是一个典型的动态规划问题。检查编辑距离问题。
您正在寻找的是所谓的编辑距离。有许多不同的类型。
来自（http://en.wikipedia.org/wiki/Edit_distance）：“在信息论和计算机科学中，两个字符串之间的编辑距离是将其中一个字符串转换为另一个字符串所需的操作数。”
这篇关于 Jazzy（java 拼写检查 API）的文章很好地概述了这些比较（这是一个类似的问题 - 提供建议的更正）http://www.ibm.com/developerworks/java/library/j-jazzy/
您可以找到最长的公共子序列，从而找到必须更改的字母。
我的直觉是您的朋友是正确的，因为没有更有效的解决方案，但这是假设您每次都在重新加载字典。如果您要保留一个正在运行的常见转换数据库，那么肯定会有一种更有效的方法来找到解决方案，但是您需要事先生成转换，并发现哪些转换有用（因为您无法生成他们全部！）可能是它自己的艺术。
bool isadjacent(string& a, string& b)
{
int count = 0; // to store count of differences
int n = a.length();
// Iterate through all characters and return false
// if there are more than one mismatching characters
for (int i = 0; i < n; i++)
{
if (a[i] != b[i]) count++;
if (count > 1) return false;
}
return count == 1 ? true : false;
}
// 存储单词和最小链长度的队列项 // 到达单词。
struct QItem
{
string word;
int len;
};
// 返回从“开始”到达“目标”的最短链的长度 // 使用最少的相邻移动次数。D是字典
int shortestChainLen(string& start, string& target, set<string> &D)
{
// Create a queue for BFS and insert 'start' as source vertex
queue<QItem> Q;
QItem item = {start, 1}; // Chain length for start word is 1
Q.push(item);
// While queue is not empty
while (!Q.empty())
{
// Take the front word
QItem curr = Q.front();
Q.pop();
// Go through all words of dictionary
for (set<string>::iterator it = D.begin(); it != D.end(); it++)
{
// Process a dictionary word if it is adjacent to current
// word (or vertex) of BFS
string temp = *it;
if (isadjacent(curr.word, temp))
{
// Add the dictionary word to Q
item.word = temp;
item.len = curr.len + 1;
Q.push(item);
// Remove from dictionary so that this word is not
// processed again. This is like marking visited
D.erase(temp);
// If we reached target
if (temp == target)
return item.len;
}
}
}
return 0;
}
// Driver program
int main()
{
// make dictionary
set<string> D;
D.insert("poon");
D.insert("plee");
D.insert("same");
D.insert("poie");
D.insert("plie");
D.insert("poin");
D.insert("plea");
string start = "toon";
string target = "plea";
cout << "Length of shortest chain is: "
<< shortestChainLen(start, target, D);
return 0;
}
复制自：https ://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/