对于数据结构的项目，我必须找到两个词之间的最短路径（如"cat"和"dog" ），每次只改变一个字母。 我们给出一个拼字单词列表中找到我们的道路使用。 例如：
cat -> bat -> bet -> bot -> bog -> dog
我已经解决了使用广度优先搜索的问题，但正在寻求更好的东西（我表示有线索的字典）。
请给我一个更有效的方法的一些想法（在速度和内存方面）。 东西荒谬和/或具有挑战性的是优选的。
我问我的朋友（他是一个大三）之一，他表示，目前没有有效的解决这个问题。 他说，我会了解为什么，当我把这些算法课程。 任何评论了？
我们必须摆脱到词。 我们不能走cat -> dat -> dag -> dog 。 我们也有打印出来的穿越。
新的答案
鉴于最近的更新，你可以尝试用汉明距离作为启发式A *。 它是因为它启发的不是去高估的距离
OLD ANSWER
您可以修改用于计算的动态程序Levenshtein距离来获得操作的顺序。
编辑：如果有一个字符串的常数，这个问题是在多项式时间内可解。 否则，它是NP-硬（这一切都没有在维基百科）..假设你的朋友都在谈论这个问题是NP难问题。
编辑：如果你的字符串的长度相等，可以使用汉明距离 。
与字典，BFS是最佳的，但所需要的运行时间成比例，其大小（V + E）。 随着N个字母，字典中可能有一个〜^ N entires，其中一个是字母的大小。 如果字典中包含的所有单词，但一个应该是在链的末端，那么你会遍历所有可能的话，但不会发现任何东西。 这是图的遍历，但规模可能会成倍大。
你可能想知道是否可以做得更快 - 浏览结构“智能”，并做到在多项式时间。 答案是，我认为，没有。
问题：
你给出一个快速的（线性）的方式，来检查单词在字典两个字U，V，并检查是否有一个序列u - > 1 - > 2 - > - > 正 - >诉
是NP难问题。
证明：花一些3SAT例如，像
（p或q或不r）和（p或不q或r）的
你会用0 000 00开始，并检查是否有可能要到2 222 22。
第一个字符将是“是我们完成”，下一个三个位将控制P，Q，R和两个下将控制条款。
允许的话是：
从0 000 00生产2 222 22，你必须这样做，以这种方式：
在四个步骤例如0 100 111 - （1）翻转适当比特。 这就需要找到一个解决方案3SAT。
（2）更改第一位为2：2 100 111这里，您将验证这确实是一个3SAT解决方案。
（3）改变2 100 111 - > 200 2 111 - > 220 2 111 - > 222 2 111 - > 222 2 211 - > 222 2 221 - > 222 2 222。
这些规则执行，你不能欺骗（检查）。 要2 222 22是可能的，只有公式是satisfable，以及检查是NP难题。 我觉得这可能是更难（#P或FNP可能），但NP-硬度足够用于这一目的，我认为。
编辑 ：您可能感兴趣的不相交集数据结构 。 这将需要能够相互达成您的字典和组词。 您也可以从每个顶点到root或其他一些顶点存储路径。 这会给你一个路径，而不是neccessarily最短的一个。
有变化的查找链接效率的方法-你可以构造一个完整的图形对每个单词的长度，或者你可以构造一个BK树 ，例如，但你的朋友是正确的- BFS是最有效的算法。
然而，有以显著改善你的运行方式：不是从源节点做一个BFS的，做两次广度优先搜索，开始在图的两端和终止时，你会发现在他们的前沿套公共节点。 你必须做的工作量大约是一半，如果你只从一个搜索到底需要什么。
您可以通过删除不正确的长度的话让它更快一点，第一。 更有限的字典将适用于CPU的缓存。 也许这一切。
此外，所有的STRNCMP比较（假设你做的一切小写）可以memcmp比较，甚至展开比较，它可以是一个加速。
你可以使用一些魔法的预处理器和硬编译为字长的任务，或滚共同字长任务的一些优化的变化。 所有这些额外的比较可以“走”为纯粹的展开乐趣。
这是一个典型的动态规划问题。 检查编辑距离问题。
你所寻找的被称为编辑距离。 有许多不同的类型。
从（ http://en.wikipedia.org/wiki/Edit_distance ）：“在信息理论和计算机科学两个字符字符串之间的编辑距离是把其中的一个到另一个所需的操作次数”
本文关于爵士（java的拼写检查API）有这些类型的比较（这是一个类似的问题-提供建议更正）的一个很好的概述http://www.ibm.com/developerworks/java/library/j-jazzy/
你能找到的最长公共子序列，并因此发现必须改变字母。
我的直觉是，你的朋友是正确的，因为没有一个更有效的解决方案，但毕竟是assumming每次都重新加载字典。 如果你要保持共同转变正在运行的数据库，那么肯定会有寻找解决一个更有效的方法，但你需要事先生成的转换，并发现哪些过渡将是有益的（因为你不能生成他们！）可能是它自己的艺术。
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/
