Word ladder implemented using stack and queue

Question

My function outputLadder function basically takes in a start and end string and generates the shortest word ladder from that.

It is iterating through a std::list containing over 3600 words read into it from a text file and seems to take a very long time.

What can I do to make my function faster while still maintaining a stack and queue implementation of the word ladder?

Here is the link to what the text file contains: http://textuploader.com/dkacm

Here is a video of the output which shows how long it takes.

Measuring it with clock() it takes about 8 seconds to find the shortest word ladder for style and crazy.

void WordLadder::outputLadder(const string &start, const string &end)
{
    stack<string> words;
    words.push(start);

    queue<stack<string>> ladder;
    ladder.push(words);

    while (!ladder.empty())
    {
        for (list<string>::iterator i = dictionary.begin(); i != dictionary.end(); ++i)
        {
            if (oneDiff(*i, ladder.front().top()))
            {
                if (*i == end)
                {
                    stack<string> output;

                    while (!ladder.front().empty())
                    {
                        output.push(ladder.front().top());
                        ladder.front().pop();
                    }

                    while (!output.empty())
                    {
                        cout << output.top() << " ";
                        output.pop();
                    }

                    cout << *i << endl;

                    return;
                }
                else
                {
                    stack<string> temp = ladder.front();
                    temp.push(*i);
                    ladder.push(temp);
                    i = dictionary.erase(i);
                }
            }
        }

        ladder.pop();
    }

    cout << "No word ladder exists for this word." << endl;
}

bool WordLadder::oneDiff(const string &dictWord, const string &stackWord)
{
    int count = 0;

    for (int i = 0; i < stackWord.size(); ++i)
    {
        if (dictWord.at(i) != stackWord.at(i))
        {
            ++count;
        }
    }

    if (count <= 1)
    {
        return true;
    }

    return false;
}

Have you actually done any performance measurements yourself? You should do that and at least tell us which part of your code eats up the most of it. — Ben Steffan
– Ben Steffan, Commented Jun 29, 2017 at 14:10

Ben Steffan · Accepted Answer · 2017-06-29 14:31:09Z

Some small improvements:

Do not use std::endl because it always forces a flush in addition to a new line, which can degrade output performance.
Prefer operator[] over at[] wherever possible. For example, in oneDiff you use dictWord.at(i) instead of dictWord[i]. The reason this is detrimental is that at() performs a bounds check (and possibly throws an exception if the bounds are violated) while operator[] does not. Since i only ever takes values smaller than stackWord.size(), you do not need at().
Prefer std::size_t for iteration variables. int may be to small to hold all indices for very large strings.
Don't use ... < something.somemethod() in a loop head, because something.somemethod() may be executed every iteration. If you know that it value does not change throughout, store its value before the loop into a variable.
oneDiff can be optimized. Since you only return whether or not the difference between characters is one or less, you can return false as soon as you have found more than one mismatch.
Although you do not give the definition of dictionary, it can be assumed that it is of type std::list<std::string> because of the iterator you are using. I would recommend replacing it with a std::vector if you are not doing a lot of insertion and deletion at random positions, because std::vector profits from cache coherency.

Stack Exchange Network

Word ladder implemented using stack and queue

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Word ladder implemented using stack and queue

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions