Finding a word ladder using Breadth First Search

Question

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 <iostream>
#include <string>
#include <unordered_set>
#include <vector>

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

    int ladderLength(string start, string end, unordered_set<string> &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 = [&](const Level& curr) -> 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 = [&](const Level& lvl) -> 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(curr.empty())    return 0;
            for(const auto& 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?

Answer 1

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.