LeetCode 126: Word Ladder II

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

Given two words (begin and end), and a dictionary's word list, find all shortest transformation sequence(s) from begin to end, such that:

Only one letter can be changed at a time.

Each transformed word must exist in the word list. Note that begin is not a transformed word. Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume begin and end are non-empty and are not the same.

Inputs

"hit"
"cog"
["hot","dot","dog","lot","log","cog"]
"hit"
"cog"
["hot","dot","dog","lot","log"]

Outputs

[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
[]

Code

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

struct Solution {
    const inline std::vector<std::vector<std::string>> findLadders(
                const std::string begin,
                const std::string end,
                const std::vector<std::string> &words
    ) {
        std::unordered_set<std::string> dict_words(words.begin(), words.end());

        if (dict_words.find(end) == dict_words.end()) {
            return {};
        }

        graph graph;
        std::vector<std::vector<std::string>> paths;
        std::vector<std::string> path = {begin};

        if (make_graph(graph, begin, end, dict_words)) {
            find_paths(graph, begin, end, path, paths);
        }

        return paths;
    }

private:

    typedef unordered_map<std::string, std::vector<std::string>> graph;

    const inline bool make_graph(
        graph &graph,
        const std::string begin,
        const std::string end,
        std::unordered_set<std::string> &dict_words
    ) {
        std::unordered_set<std::string> candidate_words;
        candidate_words.insert(begin);

        while (!candidate_words.empty()) {
            if (candidate_words.find(end) != candidate_words.end()) {
                return true;
            }

            for (std::string word : candidate_words) {
                dict_words.erase(word);
            }

            std::unordered_set<std::string> curr_word;

            for (std::string word : candidate_words) {
                std::string parent = word;

                for (int chari = 0; chari < word.size(); chari++) {
                    char character = word[chari];

                    for (int letter = 0; letter < 26; letter++) {
                        word[chari] = 'a' + letter;

                        if (dict_words.find(word) != dict_words.end()) {
                            curr_word.insert(word);
                            graph[parent].push_back(word);
                        }
                    }

                    word[chari] = character;
                }
            }

            std::swap(candidate_words, curr_word);
        }

        return false;
    }

    static const inline void find_paths(
        graph &graph,
        const std::string begin,
        const std::string end,
        std::vector<std::string> &path,
        std::vector<std::vector<std::string>> &paths
    ) {
        if (begin == end) {
            paths.push_back(path);

        } else {
            for (std::string child : graph[begin]) {
                path.push_back(child);
                find_paths(graph, child, end, path, paths);
                path.pop_back();
            }
        }
    }
};

References

• Problem

• Discuss

• Solution

Answer 1

Direct character iteration

                for (int letter = 0; letter < 26; letter++) {
                    word[chari] = 'a' + letter;

does not need to use integers. Instead,

for (char letter = 'a'; letter <= 'z'; letter++) {
    word[chari] = letter;

Answer 2

Observation

This is favorite of mine for interview.

The first thing I want a candidate to do is spot that this is solvable using Dijkstra's algorithm. :-)

You don't need to build the graph nor implement the traveling salesman to find the best solution. Much easier to implement Dijkstra. And rather than being O(n².2ⁿ) you can get O(n²).

Code Review

Prefer: std::vector<std::vector<std::string>> rather than const inline std::vector<std::vector<std::string>>.
Prefer: To pass unmodfiable parameters be const reference.
Prefer: To put the & by the type rather than the parameter.

    const inline std::vector<std::vector<std::string>> findLadders(
                const std::string begin,
                const std::string end,
                const std::vector<std::string> &words
    )

---

I have started using std::begin() and std::end() rather than using the mebers. This makes it easier to modify the code simply by changing types:

        std::unordered_set<std::string> dict_words(words.begin(), words.end());


         // I would do this:
        std::unordered_set<std::string> dict_words(std::begin(words), std::end(words));

---

Why only test end. Why not test both start and end for an early exit?

        if (dict_words.find(end) == dict_words.end()) {
            return {};
        }

---

To help distinguish between types and objects. It is normal to use an initial capitol letter in the type name (at least for user defined types).

        graph graph;

        // So I would do
        Graph  graph;

Types are really important in C++ so make them stick out.

---

This is the old style of type aliasing (yes I know the keyword is typedef. But you are creating a type alias (these are not distinct types simply two names for the same type).

    typedef unordered_map<std::string, std::vector<std::string>> graph;

    // The modern way of doing this is:
    using  graph = unordered_map<std::string, std::vector<std::string>>;

---

In the last part I would make the same comment as @Reinderien with the for loop.

        std::unordered_set<std::string> candidate_words;

Dijkstra Algorithm

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>

using Word = std::string;
struct Node // Used by the frontier queue (a priority queue)
{           // Ordered by cost;
    Node(Word const& word)
        : word(word)
        , cost(0)
    {}
    Node(Word const& word, int cost, Word parent)
        : word(word)
        , cost(cost)
        , parent(parent)
    {}

    bool operator<(Node const& rhs)  const {return std::tie(cost, word) > std::tie(rhs.cost, rhs.word);}

    Word    word;
    int     cost;
    Word    parent;
};
struct Data // Used by Found List
{           // The word is the key into the list
            // We track the number of routes to this node by tracking the parents
            // with equal cost to get to this node.

    // Used to create␣
    Data(Node const& node)
        : cost(node.cost)
    {
        if (node.parent != "") {
            parents.emplace_back(node.parent);
        }
    }
    void addParent(Word const& word)
    {
        parents.emplace_back(word);
    }

    int                 cost;
    std::vector<Word>   parents;
};
using FrontierQueue = std::priority_queue<Node>;
using FoundList     = std::map<Word, Data>;
using Route         = std::vector<Word>;
using Result        = std::vector<Route>;
using Dictionary    = std::set<Word>;

void buildResult(FoundList const& found, Word const& node, Route& route, Result& result)
{
    route.emplace_back(node);
    auto const& nodeInfo = found.find(node);

    if (nodeInfo->second.parents.size() == 0) {
        // Only start has no parents.
        result.emplace_back(route.rbegin(), route.rend());
        route.pop_back();
        return;
    }

    for(auto const& parent: nodeInfo->second.parents) {
        buildResult(found, parent, route, result);
    }
    route.pop_back();
}

std::vector<std::vector<std::string>> dijkstra(
        Word const& begin,
        Word const& end,
        std::vector<std::string> const& words)
{
    Dictionary      dictionary(std::begin(words), std::end(words));

    bool            foundEnd = false;
    int             bestCost;
    FrontierQueue   frontier;
    FoundList       found;

    frontier.emplace(begin);

    while (!frontier.empty())
    {
        Node node    = frontier.top();
        frontier.pop();

        if (foundEnd && node.cost > bestCost) {
            // We have found the end and any subsequent path will
            // be longer (as frontier is sorted by cost) so
            // we can simply stop now.
            break;
        }

        auto find = found.find(node.word);
        if (find == found.end()) {
            // First time we have seen this word add it to the found list.
            found.emplace(node.word, node);
        }
        else {
            // We have found the shortest route to this node
            if (node.cost == find->second.cost) {
                // Another route to this node that is of the same length
                find->second.parents.emplace_back(node.parent);
            }
            // No point in adding other words from this point as this was already done.
            continue;
        }

        if (node.word == end) {
            // reached the end.
            // So record the cost of getting there.
            // Other routes may equal it.
            foundEnd = true;
            bestCost = node.cost;
        }
        else {
            // Not at the end find the next words to try.
            std::string next = node.word;
            for(auto& val: next) {
                auto tmp = val;
                for(char loop = 'a'; loop <= 'z'; ++loop) {
                    val = loop;
                    if (next != node.word && dictionary.find(next) != dictionary.end()) {
                        frontier.emplace(next, node.cost + 1, node.word);
                    }
                }
                val = tmp;
            }
        }
    }

    // At this point we have found all the shortest routes to end.
    // Or there is no route to end.

    auto endNode = found.find(end);
    if (endNode == found.end()) {
        // No end node so return an empty list.
        return {};
    }

    Route   route;
    Result  result;
    buildResult(found, end, route, result);

    return result;
}

int main()
{
    std::string begin   = "hit";
    std::string end     = "cog";
    std::vector<std::string> words  = {"hot","dot","dog","lot","log","cog"};
/*
    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]
*/
    Result result = dijkstra(begin, end, words);
    for(auto const& route: result) {
        for(auto const& word: route) {
            std::cout << word << " ";
        }
        std::cout << "\n";
    }
}