a runtime error on my leetcode submission :heap use after free on address

Question

#include <bits/stdc++.h>
using namespace std;
#include <unordered_set>
#include <queue>
struct word {
    string s;
    int level;
    word(string a, int b)
        : s(a)
        , level(b)
    {
    }
};
bool isadj(string s1, string s2)
{
    int len = s1.length(), count = 0;
    for (int i = 0; i < len; i++) {
        if (s1[i] != s2[i])
            count++;
        if (count > 1)
            return false;
    }
    return count == 1 ? true : false;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
    unordered_set<string> st;
    for (string s : wordList)
        st.insert(s); // adding elements into a set
    if (st.find(endWord) == st.end())
        return 0;
    queue<word> q;
    q.push(word(beginWord, 0)); // initialising the queue

    while (!q.empty()) {
        word temp = q.front(); // pop the current string
        q.pop();
        if (temp.s == endWord)
            return temp.level;
        for (auto it = st.begin(); it != st.end(); it++) { // loop over the set to find strings at a distance of 1 and add them to the queue
            if (isadj(temp.s, *it)) // i have inserted code here to print the string *it
            {
                q.push(word(*it, temp.level + 1));
                st.erase(*it); // delete the element to avoid looping
            }
        }
    }
    return 0;
}

int main()
{
    // make dictionary
    vector<string> D;
    D.push_back("poon");
    D.push_back("plee");
    D.push_back("same");
    D.push_back("poie");
    D.push_back("plie");
    D.push_back("poin");
    D.push_back("plea");
    string start = "toon";
    string target = "plea";
    cout << "Length of shortest chain is: "
         << ladderLength(start, target, D);
    return 0;
}

The problem i am trying to solve is https://leetcode.com/problems/word-ladder/ I am unable to trace where I am using a memory that was deallocated again in my program?

The following are my attempts to debug :

I tried to run it on another online ide where the code compiles and runs successfully but gives a wrong answer . in order to debug it I have inserted some lines into my code in order to print all the strings which are at a distance of 1 for my current string. surprisingly an empty string is appearing to be in the set. Please help me in understanding where am I doing a mistake.

Answer 1

unordered_set::erase returns a value, and this returned value is important. You should not ignore it.

In your case, once you erase something from the set, it is invalid. Trying to increment it results in Undefined Behavior.

The correct approach is to replace the current iterator with the returned one, then not increment during the loop.

for (auto it = st.begin(); it != st.end(); )
    if (...) {
        // ...
        it = st.erase(*it);
    } else
        ++it;

Answer 2

After the line:

st.erase(*it); // delete the element to avoid looping

the it iterator is not valid and should not be used.

Answer 3

Your problem seems to be already addressed, but if you'd be interested, this'd also pass without using std::queue, only using std::unordered_set:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>

using ValueType = std::int_fast16_t;

static const struct Solution {
    static const int ladderLength(
        const std::string start,
        const std::string end,
        const std::vector<std::string>& words
    ) {
        std::unordered_set<std::string> words_map(std::begin(words), std::end(words));
        std::unordered_set<std::string> head;
        std::unordered_set<std::string> tail;
        std::unordered_set<std::string>* curr_head;
        std::unordered_set<std::string>* curr_tail;

        if (words_map.find(end) == std::end(words_map)) {
            return 0;
        }

        head.insert(start);
        tail.insert(end);
        ValueType ladder = 2;

        while (!head.empty() && !tail.empty()) {
            if (head.size() < tail.size()) {
                curr_head = &head;
                curr_tail = &tail;

            } else {
                curr_head = &tail;
                curr_tail = &head;
            }

            std::unordered_set<std::string> temp_word;

            for (auto iter = curr_head->begin(); iter != curr_head->end(); iter++) {
                std::string word = *iter;

                for (ValueType index_i = 0; index_i < word.size(); index_i++) {
                    const char character = word[index_i];

                    for (ValueType index_j = 0; index_j < 26; index_j++) {
                        word[index_i] = 97 + index_j;

                        if (curr_tail->find(word) != curr_tail->end()) {
                            return ladder;
                        }

                        if (words_map.find(word) != std::end(words_map)) {
                            temp_word.insert(word);
                            words_map.erase(word);
                        }
                    }

                    word[index_i] = character;
                }
            }

            ladder++;
            curr_head->swap(temp_word);
        }

        return 0;
    }
};

You might want to break it into more methods, a bit too long for a function.

---

References

• For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}.