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?

• RubberDuck: I saw this in the first post queue and just wanted to welcome you to Code Review. =)
• Loki Astari: Technically this is not a breadth first search. This is a graph search and as such Dijkstra algorithm is the best solution.
• Yue Wang: @RubberDuck Thx man~
• Yue Wang: @LokiAstari Really? I have not learned graph yet. Thx for your advice. I'll try to use Dijkstra.

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.