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 &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;unordered_set&gt;
#include &lt;vector&gt;

using namespace std;

class Solution
{
    //! O(n)
    bool is_changeable(const string&amp; lhs, const string&amp; 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&lt;string&gt;;

    int ladderLength(string start, string end, unordered_set&lt;string&gt; &amp;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 = [&amp;](const Level&amp; curr) -&gt; Level
        {
            Level ret;
            for(const auto&amp; s : curr)
                for(const auto&amp; attempt : d)
                    if(is_changeable(s,attempt))    ret.push_back(attempt);
            return ret;
        };

        //! lambda to check if end reached
        auto if_found = [&amp;](const Level&amp; lvl) -&gt; bool
        {
            for(const auto&amp; 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(curr.empty())    return 0;
            for(const auto&amp; s : curr)   d.erase(s);
            ++count;
        }

        return count + 2;
    }
};


This solution caused "Time Limit Exceeded" when tested with a reasonably big dict. It's so big that I'm not not allowed to paste here, so get it here.

How can I optimize this code to AC? Am I doing BFS right? What is the bottleneck?
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.