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.