# LeetCode 126: Word Ladder II

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



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


## 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);
}
}
{
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";
}
}

• 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. Aug 25, 2022 at 6:54