LeetCode 126:字梯II -内存超过限制
我正在尝试解决LC126问题，并获得了超过以下解决方案的内存限制。我已经看到了这里的答案--所以我也将尝试使用Dijkstra，但是我想了解为什么我的内存限制超过了，并学习如何改进我的代码。
其主要思想是: BFS在路径上，即从起始字开始构建中间路径，如果没有访问，则用邻居扩展这些路径。只保留最短长度的路径。
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
vector<vector<string>> res;
unordered_set<string> wordsList(wordList.begin(), wordList.end());
if (wordsList.count(endWord) == 0) {
return res;
}
unordered_set<string> visited;
queue<vector<string>> q;
q.push(vector<string>({beginWord}));
int min_len = wordList.size() + 1;
unordered_map<string, vector<string>> neigh;
for (const auto& wd: wordsList) {
neigh[wd] = getNeighbors(wd, wordsList);
}
neigh[beginWord] = getNeighbors(beginWord, wordsList);
while (! q.empty()) {
vector<string> crtPath = q.front();
q.pop();
string lastNode = crtPath.back();
visited.insert(lastNode);
for (const string& nn: neigh[lastNode]) {
if (visited.count(nn) != 0) {
continue;
}
vector<string> newPath(crtPath);
newPath.emplace_back(nn);
if (nn == endWord) {
if (newPath.size() == min_len) {
res.push_back(newPath);
}
else if (newPath.size() < min_len) {
res = {newPath};
min_len = newPath.size();
}
}
else {
if (newPath.size() <= min_len) {
q.push(newPath);
}
}
}
}
return res;
}
vector<string> getNeighbors(const string& node, const unordered_set<string>&nodes) {
vector<string> result;
string word = node;
for (int ii = 0; ii < node.length(); ++ii) {
char old_char = word[ii];
for (char ch = 'a'; ch <= 'z'; ++ch) {
if (ch == old_char) {
continue;
}
word[ii] = ch;
if (nodes.count(word) != 0) {
result.emplace_back(word);
}
}
word[ii] = old_char;
}
return result;
}回答 2
Code Review用户
发布于 2022-08-24 22:32:38
启用编译器警告并修复所有这些警告(
)。
我的编译器警告不同大小和符号的整数之间的比较。这是因为您将int用于循环索引和min_len，但是.length()和.size()返回一个std::size_t。确保您在那里也使用std::size_t。而且，std::size_t通常是用于任何大小、计数或索引的正确类型。
或者，使用range-for循环和auto来避免为这类事情指定类型。在getNeighbors()中，您可以编写：
for (auto& cur_char: node) {
auto old_char = cur_char;
...
cur_char = old_char;
}在findLadders()中：
auto min_len = wordList.size() + 1;内存使用
您的内存限制超过了，因为您使用的内存比必要的多。然后，您应该想知道您是否使用了正确的算法、该算法的正确数据结构，以及您是否正在制造不必要的(临时)的东西副本。
让我们从后者开始:您得到了wordList，但是您希望这些文件在std::unordered_set中快速查找。这是可以理解的，但现在你正在复制所有的文字。原则上，您可以创建一个只存储对wordList中字符串的引用的集合，这样就可以避免在副本上浪费内存，但不幸的是，这样做并不容易。暂时忘了这点吧。
另一个问题是，您正在创建多个数据结构，这些数据结构都是以单词为索引的:有wordsList、visited和neigh。除了现在每个单词至少重复三次之外，您还拥有三个容器的簿记开销。我将创建一个单独的std::unordered_map，并自己创建struct来保存与单个单词相关的所有数据：
struct WordInfo {
bool visited;
std::vector<std::string> neighbors;
};
std::unordered_map<std::string, WordInfo> words;
for (auto& word: wordList)
words[word] = {};代码中有几个字符串向量。这些更改可以是字符串引用的向量。或者使用std::reference_wrapper将引用存储在容器中，如下所示：
std::vector<std::reference_wrapper<std::string>> result;或者可以考虑将迭代器存储到words中：
std::vector<decltype(words)::iterator> result;或原始wordList中的索引：
std::vector<std::size_t> result;另一个问题是，在开始使用BFS算法之前，您正在计算wordList中每个单词的邻居集，即使在广度优先搜索过程中永远不会到达这些单词！所以您需要存储的O(W^2 L)，其中W是单词的数量，L是单词的长度。但是这是非常不必要的:当你访问一个单词时，你只需要知道这个单词的邻居列表。
然后是BFS算法本身。为什么你需要“只保留最短长度的路径”？如果是真正的BFS，那么当您到达endWord时，您有一条最短的路径，而且您还没有看到任何较长的路径，否则您的算法不是宽度优先。您也不需要存储所有路径；如果您只存储每个已访问节点的前身，那么在找到一个endWord时，您就可以沿着前面的路径走回去，直到到达startWord为止，这就是所需的路径之一(反向)。找到一个endWord后，只需完成队列，而不向其推送新条目。
注意，Dijkstra在只有相同权重的边的图上的算法等价于BFS。
内存使用与性能
有时，在快速但需要内存的算法和速度慢但节省内存的算法之间需要进行权衡。为了向您展示内存使用率有多低，可以考虑变性人向量wordList，对于每个置换检查其中是否有从beginWord到endWord的有效路径，并检查其长度：
std::size_t pathLength(const string& beginWord, const string& endWord, const vector<string>& wordList) {
/* Return length of path if there is a valid path
at the start of wordList, otherwise return wordList.size(). */
...
}
auto findLadders(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
std::vector<std::vector<std::string>> result;
auto minSize = wordList.size();
std::sort(wordList.begin(), wordList.end());
// Find the length of the shortest paths
do {
minSize = std::min(minSize, pathLength(beginWord, endWord, wordList));
} while (std::next_permutation(s.begin(), s.end())
// Gather all the shortest paths
do {
if (pathLength(beginWord, endWord, wordList) == minSize) {
result.emplace_back(wordList.begin(), wordList.begin() + minSize);
}
} while (std::next_permutation(s.begin(), s.end())
return result;
}除了输入参数和返回值之外，上面的代码只需要几个微小的变量。不幸的是，它运行得非常慢。
Code Review用户
发布于 2022-08-25 06:48:05
焦点搜索
该算法是非常野蛮的，在我们充分探索周围的空间开始词的所有方向。这就自然而然地形成了一大群候选人，特别是在通常情况下，结束词与起始词不共享字母。
我们可以通过使用距离度量来减少搜索空间，对候选对象进行排序:只需计算与末尾单词相同的字母即可。虽然这只是告诉我们达到目标的最小步骤数(而不是上限)，但这是一个有用的启发，可以让我们首先考虑最可能的路径。一旦一条路径被发现，它就允许我们消除那些不可能更短的路径。
这是相同的原则，在地理路由，所以应该不难找到相关的教育材料，以帮助实施。
https://codereview.stackexchange.com/questions/279096
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号