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

• I saw this in the first post queue and just wanted to welcome you to Code Review. =) – RubberDuck Nov 4 '14 at 1:41
• Technically this is not a breadth first search. This is a graph search and as such Dijkstra algorithm is the best solution. – Martin York Nov 4 '14 at 3:05
• @RubberDuck Thx man~ – Yue Wang Nov 4 '14 at 3:06
• @LokiAstari Really? I have not learned graph yet. Thx for your advice. I'll try to use Dijkstra. – Yue Wang Nov 4 '14 at 3:09

## 1 Answer

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.