在一个数据结构项目中，我必须找到两个单词之间的最短路径（例如"cat"和"dog"），每次只更改一个字母。我们被提供了Scrabble单词列表以用于查找路径。例如：
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题，但是希望找到更好的方法（我用字典树表示了字典）。
请给我一些更高效的方法（以速度和内存为基准）。 偏向于荒谬和/或具有挑战性。
我问过我的一个朋友（他是初学者），他说没有有效的解决方案。 他说当我上算法课时，我就会知道为什么。 对此有任何评论吗？
我们必须从一个单词移动到另一个单词。 我们不能像“cat->dat->dag->dog”那样走。 我们还必须打印出遍历路径。
使用字典，BFS是最优的，但所需的运行时间与其大小（V+E）成正比。对于n个字母，字典可能有~a^n个条目，其中a是字母表大小。如果字典包含除应该在链末尾的单词之外的所有单词，则您将遍历所有可能的单词，但不会找到任何内容。这是图形遍历，但大小可能呈指数增长。
您可能想知道是否可能更快地浏览“智能”结构并在多项式时间内完成它。答案是，我认为不能。
问题：
您可以快速（线性地）检查单词是否在字典中，给定两个单词u，v并检查是否存在序列u->a1->a2->...->an->v。
是NP难题。
证明：取一个3SAT实例，例如
(p或q或not r)且(p或not q或r)
您将从0 000 00开始，并要检查是否可能转到2 222 22。
第一个字符将是“我们完成了”，接下来的三个位将控制p，q，r，接下来的两个位将控制子句。(3) 将 2 100 111 改为 2 200 111，然后改为 2 220 111，再改为 2 222 111，然后改为 2 222 211，最后改为 2 222 221，最终改为 2 222 222。
这些规则强制执行了你不能作弊（检查）。只有当公式可满足时，才能到达2 222 22，并且检查它是NP难题。我觉得这可能会更难（可能是#P或FNP），但是我认为NP难度已经足够了。
编辑：您可能会对不相交集数据结构感兴趣。这将获取您的字典并分组可以从彼此到达的单词。您还可以存储从每个顶点到根或其他顶点的路径。这将为您提供一条路径，不一定是最短的路径。
寻找链接有不同效率的方法 - 您可以为每个单词长度构建完整的图，也可以构建BK-Tree等数据结构，但您的朋友是对的 - BFS算法是最有效的。
然而，有一种方法可以显着提高运行时间：不要从源节点进行单个BFS，而是从图的两端开始进行两个广度优先搜索，并在它们的前沿集中找到共同节点时终止。您需要完成的工作量大约是仅从一端搜索时所需工作量的一半。
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;
};
// 返回从“start”到“target”的最短链长度，使用最少的相邻移动。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/
我的直觉是你的朋友是正确的，因为假设你每次都重新加载字典，那么就没有更有效的解决方案了。如果你能保持一个常见转换的运行数据库，那么肯定会有更有效的方法来找到解决方案，但你需要事先生成转换，并发现哪些转换是有用的（因为你不能生成所有转换！），这可能是一门艺术。
def word_ladder(begin: str, end: str, dictionary: list[str]) -> list[str]:
def wildcards(i: int) -> Iterator[str]:
word = dictionary[i]
for j in range(len(word)):
yield f"{word[:j]}_{word[j + 1:]}"
if end not in dictionary:
return []
graph: dict[str, list[int]] = defaultdict(list)
for i in range(len(dictionary)):
for w in wildcards(i):
graph[w].append(i)
dictionary.append(begin)
to_visit = deque([(len(dictionary) - 1, -1)])
visited: set[int] = set()
path: dict[int, int] = {}
end_idx = -1
while to_visit:
word, parent = to_visit.popleft()
if word in visited:
continue
visited.add(word)
path[word] = parent
if dictionary[word] == end:
end_idx = word
break
for w in wildcards(word):
for neighbor in graph[w]:
if neighbor not in visited:
to_visit.append((neighbor, word))
result: deque[int] = deque()
while 0 <= end_idx < len(dictionary):
result.appendleft(end_idx)
end_idx = path[end_idx]
return [dictionary[i] for i in result]