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.
