3
\$\begingroup\$

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?

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.