2
\$\begingroup\$

Leet Question

Update Leet Code: 127. Word Ladder (Part 2)

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord.

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Have done this question in several ways.
Can seem to get better than beating 60% of people.
Looking for some help in optimizing this.

Rather than use several questions, I will post the original version of my code then detail the optimizations I have since done. Let me know if you have other suggests on optimizations potentially algorithmic.

This looks to me like a classic Dykstra's algorithm.
So below I have simply implemented that as a naive first attempt.

Version 1: Time 628

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string> const& wordList) {

        using Word      = std::string;
        using Dict      = std::set<Word>;
        using Item      = std::tuple<int, Word>;
        using Boundry   = std::priority_queue<Item, std::vector<Item>, std::greater<Item>>;

        Dict    words{std::begin(wordList), std::end(wordList)};
        Dict    used;
        Boundry boundry;

        boundry.push({1, beginWord});
        while (!boundry.empty())
        {
            Item   top = boundry.top();
            boundry.pop();

            Word    word = std::get<1>(top);
            int     len  = std::get<0>(top);
            if (word == endWord) {
                return len;
            }

            if (used.insert(word).second == false){
                continue;
            }

            for (char& l: word) {
                char tmp = l;

                for (char loop = 'a'; loop <= 'z'; ++loop) {
                    l = loop;

                    auto find = words.find(word);
                    if (find != words.end() && used.find(word) == used.end()) {

                        boundry.push({len + 1, *find});
                    }
                }

                l = tmp;
            }
        }

        return 0;
    }
};

Version 2 Time: 185

std::set has a ln(n) look up complexity. So maybe we can improve this by using std::unordered_set.

            using Dict      = std::set<Word>;

Changed to:

            using Dict      = std:: unordered_set<Word>;

Version 3: Time 179

Lets not copy the strings around everywhere, so change std::string into std::string_view. This needs some other minor changes to the code as the view we were getting is constant. But the changes are minor.

But no significant decrease in time. So; looking more closely at the question, I see that all words are less then 10 characters long for all problems. This means that the short string optimization is doing a great job and we are not seeing any memory allocation here.

        using Word      = std::string;

Changed to:

        using Word      = std::string_view;

Code Changes:

        Boundry boundry;
        std::string word    = beginWord;    // Added this line.
                                            // Add a single mutable string that
                                            // we use for all manipulations.
                                            // Note all words have to be the same
                                            // length as the rules don't allow for
                                            // adding letters.

        boundry.push({1, beginWord});
        while (!boundry.empty())
        {
            Item   top = boundry.top();
            boundry.pop();

            // Changed these two lines.
            // Get a reference to the word. Then copy
            // Into the mutable section for doing manipulations.
            Word   wordRef = std::get<1>(top);
            std::copy(std::begin(wordRef), std::end(wordRef), std::begin(word));

Version 4. Time 145 ms

I thought about improving the algorithm. The reason for having a priority queue is that different paths in the graph can have different lengths. So any new nodes you add to the boundary list have to be added into the list at the correct location, which may be shorter than routes you have already found.

But in this situation, all paths have a length of 1. So this is never going to happen so I can simply add the items onto the end of the list and the list will automatically be sorted. To reduce the need to reorder the list, let's not even remove items from the array and just inclemently work through the list:

        using Boundry   = std::priority_queue<Item, std::vector<Item>, std::greater<Item>>;

     Change to:

        using Boundry   = std::vector<Item>;

Then:

        Boundry boundry;

        boudry.push({1, beginWord});
        while (!boudry.empty())
        {
            Item   top = boudry.top();


    Change To:

        Boundry boundry;
        boundry.reserve(wordList.size() * 4);

        boundry.emplace_back(1, beginWord);
        for (std::size_t loop = 0; loop < boundry.size(); ++loop)
        {
            Item&   top = boundry[loop];

Version 5: Time 126

The test to see if we have reached the end. This is done when we pull items out of the boundry list. But Since the edge lengths are always 1 the first time we see the endWord it will be the correct length. So move the test into the inner loop so as soon as we see it we can return.

So the final solution I have is:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string> const& wordList) {

        using Word      = std::string_view;
        using Dict      = std::unordered_set<Word>;
        using Item      = std::tuple<int, Word>;
        using Boundry   = std::vector<Item>;

        Dict    words{std::begin(wordList), std::end(wordList)};
        Dict    used;
        Boundry boundry;
        boundry.reserve(wordList.size() * 4);
        std::string word    = beginWord;

        boundry.emplace_back(1, beginWord);
        for (std::size_t loop = 0; loop < boundry.size(); ++loop)
        {
            Item&   top = boundry[loop];

            Word   wordRef = std::get<1>(top);
            std::copy(std::begin(wordRef), std::end(wordRef), std::begin(word));

            int    len  = std::get<0>(top);

            if (used.insert(word).second == false){
                continue;
            }

            for (char& l: word) {
                char tmp = l;

                for (char loop = 'a'; loop <= 'z'; ++loop) {
                    l = loop;
                    auto find = words.find(word);
                    if (find != words.end() && used.find(word) == used.end()) {

                        if (word == endWord) {
                            return len + 1;
                        }
                        boundry.emplace_back(len + 1, *find);
                    }
                }

                l = tmp;
            }
        }

        return 0;
    }
};

Other Things I have tried.

I tried using std::string* rather than std::string_view does not seem to have any significant effect.

I tried replacing std::tuple<int, Word> with struct Info {int x;Word y;}; again no significant effect.

I tried changing the order of letters from a -> z to a most common letters first approach.

Any other suggestions most welcome.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

Thank you for describing the journey, it is entertaining and informative. "I thought X would shave off some time!", but no. Yeah, we've all been there.


I didn't notice that you filter the words list down to word lengths that match the starting length. But maybe the problem setup does that filtering for you already.


                for (char loop = 'a'; loop <= 'z'; ++loop) {

There's some things we're not taking advantage of, here. And I don't mean that 'z' is unlikely to win.

We have IDK maybe 30 K ten-character words to worry about? So there is some graph G with 30,000 nodes and a fairly small out-degree from any given node. If we assume the problem space sticks to English dictionary words we could pre-compute it. If the problem space "mostly" adheres to Webster's we could incorporate such a graph into an online solution and expect some savings.

An edge is induced by a single-character substitution. So for example "fee" -> "fie" -> "foe" all have distance == 1.

Think about an anagram solver, where the canonical sorted representation for those words would be {"eef", "efi", "efo"}, or possibly {"e": 2, "f": 1} and the others with single counts.

We wish to explore a graph. It would be convenient if all the out-edges were lexically sorted so we could explore them systematically.

def: let "sorted letters" be hash of a word, so e.g. "fee" --> "eef". (Yes, there will be collisions.)

Order the list of words by sorted letters. Rather than making 26 probes, simply visit the next entry.

Additionally, once you have traversed through a few letters, it seems it would be helpful to recompute a sorted list which filters out those no-longer-relevant letters.

Sorting by observed or anticipated frequency ("etaoinshrdlu") should be helpful.

Preferring to initially explore popular letters (roughly, "vowels first!") should also help with rapidly pruning the graph.

\$\endgroup\$
3
\$\begingroup\$

About the algorithm

This looks to me like a classic Dijkstra's algorithm. […] But in this situation, all paths have a length of 1. So this is never going to happen so I can simply add the items onto the end of the list and the list will automatically be sorted.

Indeed, if all paths have length 1 then you can use a breadth-first search instead, which you eventually implemented.

Inside the outer for-loop, you are basically trying to find the next set of words which are one hop away from the top word. This takes \$O(A \cdot L)\$ time, where \$A\$ is the size of the alphabet used (only 26 in this case, but this would be larger if upper case and other characters would be possible), and \$L\$ is the length of the words. In the examples given on the LeetCode website, the words had length 3, so you are doing \$26 \cdot 3 = 78\$ calls to words.find(), but the word list only has 6 words. So you could also have compared the six words to see which ones differ from top by one character. That would only take \$N \cdot L\$ time, where \$N\$ is the number of words in the word list. Doing words.find() is also more expensive than just comparing two characters, so your strategy only pays off for inputs where \$N \gg A\$.

Since you know \$N\$ and \$A\$ up front, you can implement both strategies and have your code choose the better one.

J_H has suggested yet another way to approach the problem.

Reduce the overhead from your containers

While a std::string_view is smaller than a std::string, it still takes some space. And std::unordered_set will typically allocate memory for each individual item, and needs to store additional metadata. So Dict used seems like it will waste a lot of memory, when you only need a bool per word to track if it is already used or not. Or perhaps you don't even need that; you can perhaps use the path length. Consider:

using Dict = std::unordered_map<Word, int>;
using Boundry = std::vector<Dict::iterator>;
Dict words;
Boundry boundry;
std::string word = beginWord;

for (auto& word: wordList)
   words[word] = 0;

auto [beginIt, _] = words.try_emplace(beginWord, 1);
boundry.push_back(beginIt);

for (std::size_t loop = 0; loop < boundry.size(); ++loop) {
    auto top = boundry[loop];
    Word wordRef = top->first;
    word = wordRef;

    if (words[word] != 0) {
        continue;
    }

    …
}
\$\endgroup\$
3
  • \$\begingroup\$ Actually trying something very similar to this now. Have it down to 102. \$\endgroup\$ Feb 19, 2023 at 1:19
  • \$\begingroup\$ Still need to cut another 20ms off to be near the top. \$\endgroup\$ Feb 19, 2023 at 1:20
  • \$\begingroup\$ Even tried removing the boundry and embedding the list into the value part of the Dict so we can have a length and the next value in the chain. But that does not help much. \$\endgroup\$ Feb 19, 2023 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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