Finding a word ladder using Breadth First Search

This is a LeetCode problem called Word Ladder:


Given two words (start and end), and a dictionary, find the length of
shortest transformation sequence from start to end, where only one letter can be
changed at a time. Each intermediate word must
exist in the dictionary For example,


Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]


As one shortest transformation is
"hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.


Note:


Return 0 if there is no such transformation sequence. All words
have the same length. All words contain only lowercase alphabetic
characters.

My solution:

```
#include
#include
#include
#include

using namespace std;

class Solution
{
//! O(n)
bool is_changeable(const string& lhs, const string& rhs)
{
size_t count = 0;
for(auto l = lhs.cbegin(), r = rhs.cbegin(); l != lhs.cend(); ++l,++r)
if(l != r) ++count;
return count == 1;
}

public:
using Level = vector;

int ladderLength(string start, string end, unordered_set &dict)
{
if(dict.empty()) return 0;

auto d = dict;
d.erase(start);
d.erase(end);
if(d.empty()) return 2;

//! lambda to make next level
auto next_level = & -> Level
{
Level ret;
for(const auto& s : curr)
for(const auto& attempt : d)
if(is_changeable(s,attempt)) ret.push_back(attempt);
return ret;
};

//! lambda to check if end reached
auto if_found = & -> bool
{
for(const auto& s : lvl)
if(is_changeable(s,end)) return true;
return false;
};

/**
* @brief top abstraction layer
*/
size_t count = 0;
for(auto curr = Level{start}; !if_found(curr); curr = next_level(curr))

If you worry about the performance, the first thing to try is to hook up the profiler. Besides that, constructing another Ladder at each level seems wasteful.

-
is_changeable is named misleadingly; my first impression was that you are testing a mutability of something. It turned out that the method test for a Hamming distance to be 1. I recommend to name it hamming_distance, make it return int (or size_t or whatever you find appropriate) ant let the client test the result for 1.

-
Use of lambdas borders to abuse. If you feel a need to comment what lambda is doing, it is a strong indication that the lambda wants to have a name, i.e. be a normal function.

StackExchange Code Review Q#68813, answer score: 2