LeetCode 126: Word Ladder II -- Memory limit exceeded

Question

I am trying to solve LC126, and got a memory limit exceeded for the following solution. I've seen the answer here -- so I'll try to use Dijkstra as well, but I would like to understand why I get the memory limit exceeded, and to learn how I could improve my code.

The main idea: BFS on paths, i.e. from start word, build the intermediate paths starting with the start word, then, extend these paths with neighbors, if not visited. Keep only paths of shortest length.

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;
}

Answer 1

Enable compiler warnings and fix all of them

My compiler warns about comparisons between integers of different sizes and signedness. This is because you are using int for loop indices and min_len, but .length() and .size() return a std::size_t. Make sure you also use std::size_t there. Also, std::size_t is usually the right type to use for everything that is a size, count or index.

Alternatively, use range-for loops and auto to avoid having to specify a type for such things to begin with. In getNeighbors(), you could write:

for (auto& cur_char: node) {
    auto old_char = cur_char;
    ...
    cur_char = old_char;
}

And in findLadders():

auto min_len = wordList.size() + 1;

Memory usage

You get memory limit exceeded because you are using more memory than necessary. You should then wonder about whether you are using the right algorithm, the right datastructures for that algorithm, and whether you are making unnecessary (temporary) copies of things.

Let's begin with the latter: you are given wordList, but you want these to be in a std::unordered_set for quick lookups. That is understandable, but now you are making a copy of all the words. In principle, you could create a set that just stores references to the strings inside wordList, so you avoid wasting memory on copies, but unfortunately that's not trivial to do. Let's forget that for now.

Another issue is that you are creating multiple data structures that are all indexed on words: there's wordsList, visited and neigh. Apart from now duplicating every word at least three times, you also have the bookkeeping overhead of three containers. I would create a single std::unordered_map, and create struct yourself to hold all the data related to a single word:

struct WordInfo {
    bool visited;
    std::vector<std::string> neighbors;
};

std::unordered_map<std::string, WordInfo> words;

for (auto& word: wordList)
    words[word] = {};

You have several vectors of strings in your code. Those could be changes to be vectors of references to strings. Either use std::reference_wrapper to store references in containers, like so:

std::vector<std::reference_wrapper<std::string>> result;

Or you could consider storing iterators into words:

std::vector<decltype(words)::iterator> result;

Or indices into the original wordList:

std::vector<std::size_t> result;

Another issue is that before you are starting with the BFS algorithm, you are calculating the set of neighbors for every word in wordList, even if you would never reach those words during the breadth-first-search! So you need up to \$O(W^2 L)\$ of storage, where \$W\$ is the number of words and \$L\$ is the length of the words. But this is quite unnecessary: you only need to know the list of neighbors of a word when you visit that word.

Then there's the BFS algorithm itself. Why do you need to "keep only paths of shortest length"? If it's truly BFS, then the moment you reach the endWord, you have a path with the shortest length, and you haven't seen any paths with a longer length yet, otherwise your algorithm is not breadth-first. You also don't need to store all paths; if you just store the predecessor of every visited node, then the moment you find an endWord you can just walk back along the predecessors until you reach startWord, and that's then one of the desired paths (in reverse). Once you have found one endWord, just finish the queue without ever pushing new entries to it.

Note that Dijkstra's algorithm on a graph with only edges of the same weight is equivalent to BFS.

Memory usage vs. performance

Sometimes there are trade-offs to be made between fast but memory-hungry algorithms, and slow but memory-efficient algorithms. Just to show you how low you can go with memory usage, consider that you can just permute the vector wordList, and for each permutation check if there is a valid path from beginWord to endWord in it, and check its length:

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;
}

Apart from the input parameters and return value, the above code only needs a few tiny variables. Unfortunately, it runs very slow.

Answer 2

Focus the search

The algorithm is very brute-force, in that we fully explore the space around the start word in all directions. This naturally builds up a huge set of candidates, particularly in the common case where the end word shares no letters with the start word.

We can reduce the explored search space by using a distance metric to prioritise candidates: just count the letters in common with the end word. Although this only tells us the minimum number of steps to reach the target (rather than an upper bound), it's a useful heuristic to allow us to consider the most likely paths first. And once a path is discovered, it allows us to eliminate paths that cannot possibly be shorter.

This is exactly the same principle used in geographical routing, so it shouldn't be too hard to find relevant educational material to help with implementation.