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(n2.2n) you can get O(n2).

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

• Toby Speight: The best (most general) way to use std::begin() and std::end() is by using them (within a small scope), so that ADL can find implementations belonging to a type's namespace if provided.