Leet Code: 127. Word Ladder (Part 2)

Question

Original Question:

Leet Question

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.

Let me know if you have other suggests on optimizations potentially algorithmic.

Version 6: Time 139 ms

Continuing on from the original question:

I replaced std::vector<Item> with std::deque<Item>.

This does not really gain us any benifit. But it is the more "proper" way of doing things as we can add to the tail and drop items from the front once used.

        using Boundry   = std::vector<Item>;

        ....

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


 Changed to:

        using Boundry   = std::deque<Item>;

        ....
        boundry.emplace_back(1, beginWord);
        while (!boundry.empty())
        {
            Item   top = boundry.front();
            boundry.pop_front();

Version 7: Time 108

I noticed that the words and used containers were basically the same thing. So rather than using two containers lets us a single container. Need to add some information to capture some state (as before used was holding the state change informaiton by adding new values).

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

  Changed to:

        using Word      = std::string;
        using Dict      = std::unordered_map<Word, int>;
        using Boundry   = std::deque<Word>;

We will now use the Dict to hold information about all words. The int value will contain. 0 => not searched. Negative => Found and have a value but not searched. Positive => Found and have a value and searched.

Note: The Boundry now only contains the words themselves, as the cost to get to a node is stored in the map.

Enough of a change to add the whole thing:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string> const& wordList) {
        using Word      = std::string;
        using Dict      = std::unordered_map<Word, int>;
        using Boundry   = std::deque<Word>;

        Dict    words;
        for (auto const& word: wordList) {
            words.insert({word, 0});
        };
        Boundry boundry;

        boundry.emplace_back(beginWord);
        words[beginWord] = -1;               // Length 1 not searched.
        while (!boundry.empty())
        {
            Word   word  = boundry.front();
            auto   input = words.find(word);
            int&   len   = input->second;
            boundry.pop_front();

            if (len > 0) {
                // Length greater than zero so we have already searched from this node.
                // So simply continue.
                continue;
            }

            // We are about to search from this node so make the values positive.
            len = -len;

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

                for (char loop = 'a'; loop <= 'z'; ++loop) {
                    l = loop;
                    auto find = words.find(word);
                    // Simplified this test by only doing one search
                    // If found and the value is 0 then we need to do something
                    // otherwise it has been taken care of already.
                    if (find != words.end() && find->second == 0) 
                    {
                        if (word == endWord) {
                            return len + 1;
                        }

                        boundry.emplace_back(find->first);
                        find->second = -(len + 1);
                    }
                }

                l = tmp;
            }
        }

        return 0;
    }
};

Version 8: Time 102

In the boundry list rather than storing the word. Let us store the iterator into words.

class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string> const& wordList) {
    
            using Word      = std::string;
            using Dict      = std::unordered_map<Word, int>;
            using Boundry   = std::deque<Dict::iterator>;
    
            Dict    words;
            for (auto const& word: wordList) {
                words.insert({word, 0});
            };
            auto [beginIt, _] = words.insert({beginWord, 0});
            Boundry boundry;
    
            boundry.emplace_back(beginIt);
            beginIt->second = -1;
            while (!boundry.empty())
            {
                Word   word  = boundry.front()->first;
                int&   len   = boundry.front()->second;
                boundry.pop_front();

                if (len > 0) {
                    continue;
                }
                len = -len;
    
                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() && find->second == 0) 
                        {
                            if (word == endWord) {
                                return len + 1;
                            }

                            boundry.emplace_back(find);
                            find->second = -(len + 1);
                        }
                    }
    
                    l = tmp;
                }
            }
    
            return 0;
        }
    };

Version 9: 102 (but reduced memory usage significantly)

Now I am starting to get into hacky areas. Where I start messing with pointers and doing stuff that I know will work but goes against my C++ principles (i.e. I am using C). It did not give me any time benefit but significantly reduced the amount of memory used (so I have included it here).

I got rid of the boundry stack. Instead, I added another value into the words map where I stored the a pointer to the next stored item in the words list.

        using Dict      = std::unordered_map<Word, std::pair<int, void*>>;

Some funky looking assignments to get the address and chain them together.

                        ValuePtr newEndOfChain = &(*find);
                        endChain->second.second = newEndOfChain;
                        endChain = newEndOfChain;

See details below for final version.

Version 10: 92

Rather than do a string comparison for endWord. Since I know endWord is the words map let us simply compare the iterators into the map to see if the iterator I have found is equivalent to the iterator of the endWord.

class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string> const& wordList) {
    
            using Word      = std::string;
            using Dict      = std::unordered_map<Word, std::pair<int, void*>>;
            using Value     = Dict::value_type;
            using ValuePtr  = Value*;
    
            Dict    words;
            for (auto const& word: wordList) {
                words.insert({word, {0, nullptr}});
            };
            auto findEnd = words.find(endWord);
            if (findEnd == words.end()) {
                return 0;
            }
 
            auto [beginIt, _] = words.insert({beginWord, {0, nullptr}});
            // Note: Insert can fail (if it is already in there)
            //       So need to set the length as the next statement.
            beginIt->second.first = -1;

            // Set up the loop iteration.
            ValuePtr loop = &(*beginIt);
            ValuePtr endChain = loop;

            for (;loop; loop = reinterpret_cast<ValuePtr>(loop->second.second))
            {
                Word   word  = loop->first;
                int&   len   = loop->second.first;

                if (len > 0) {
                    continue;
                }
                len = -len;

                for (char& l: word) {
                    char tmp = l;
    
                    for (char loop = 'a'; loop <= 'z'; ++loop) {
                        l = loop;
                        auto find = words.find(word);
                        if (find == findEnd) {
                            return len + 1;
                         }

                        if (find != words.end() && find->second.first == 0) 
                        {
                            find->second.first = -(len + 1);

                            // Add Item to the end of the chain for the loop.
                            ValuePtr newEndOfChain = &(*find);
                            endChain->second.second = newEndOfChain;
                            endChain = newEndOfChain;
                        }
                    }
    
                    l = tmp;
                }
            }
    
            return 0;
        }
};

More

I have tried progressively dertier hacks to try and get this faster. Nothing has made a significant change after this. Anybody can help make this faster would love to see what you tried.

Best run is beating 75% of other entries and using less space than 97% of entries. If I can reduce run time by 5ms to below 87ms it looks like we would be in the top 5%. But the best algorithms seem to be 33 ms.

Answer 1

I'll be reviewing solution 10. I'll focus just on the style, it seems you are having a great time trying various optimizations yourself.

Naming things

Your variables have terrible names, not least because you are very inconsistent in how you name things. There's beginIt, which is clearly an iterator, but why is it findEnd and not endIt?

Most variables are full words, but then there's l. It's a character in word, so if you really want a short variable name, I'd at least expect it to be c. But it's better to just name it character. Or maybe you meant it to stand for letter?

tmp is such a generic name that doesn't describe at all what it represents. Sure it's "temporary", but so are most variables in your code. Since it's the original value of the character you are modifying, maybe originalCharacter would be better.

loop: another very generic name, that might be confusing because it's not a loop at all, rather a loop iterator. Also, there's two loops, one shadowing the other. It makes the code really hard to understand. Maybe the outer one could be called wordIt, and the inner one replacementCharacter?

Use of type aliases

Using type aliases can be helpful, but be careful that they don't unnecessarily obscure the original types. The names for the aliases should also be meaningful. Word and Dict are ok-ish, but Value is again such a generic name. A value of what? Even DictEntry would be better, as it would at least tell you it is an item living in a Dict, but it still doesn't really tell you what's stored in it.

If you have a type alias Value, do you need a ValuePtr? Why not explicitly write Value*?

Make sure names are concise, meaningful and accurate. Well chosen names go a long way toward self-documenting the code.

Prefer declaring struct over using a std::pair

Related to self-documentation: a struct is better than a std::pair; the former has a name for the whole struct (so no need for using Value = …), and names for each of its members. With std::pair you end up with the very generic .first and .second, which makes the code hard to read.

Getting rid of reinterpret_cast<>()

Use of reinterpret_cast<>() and void* is a code smell since it bypasses type-safety. Try to get rid of it where possible.

We can do this by switching from std::unordered_map to std::unordered_set. Make a struct that contains the word, path length and pointer to the next entry in the list. Then create a std::unordered_set out of that, and use a custom hash and equality function to make sure it only considers the word. So:

struct DictEntry {
    Word word;
    int length;
    DictEntry* next;
};

std::unordered_set<DictEntry> dict(…);

It's easier in C++20 where find() is a template, so you can pass it a Word instead of a dummy DictEntry if you add an overload for the equality operator that takes a Word as a parameter.

It won't win any beauty contests either, and is a bit more involved than your void* solution.

Simplify the code by creating helper functions

There are three nested for-loops in your code, making it quite complex. Consider creating some helper functions to reduce the amount of code and the nesting level inside ladderLength(). Since functions have names, this again helps with self-documenting the code as well.