Theo's Typesafe Cult•3mo ago

help with a leetcode problem

Trying to complete leetcode 14 and keep running into the DEADLYSIGNAL error. I know the code is very messy and brute force but I am trying to do it without copy pasting solutions.

Solution:

Jump to solution

43 Replies

ongonOP•3mo ago

@sidge if you want to take a look at it. I looked up DEADLYSIGNAL and im assuming it cause of an "out-of-bounds access" which I tried to fix with the IF statement inside of the while loop but it didn't change anything. also I can already see I messed up the prefix creation.

Vutinberg•3mo ago

is that "while" supposed to have a single = sign?

sidge•3mo ago

Yeah I’m not a c++ guy so idk that error I also don’t understand the while loop nested inside the two for loops

Vutinberg•3mo ago

(oh yeah I didn't even see that, I just looked at the error message then checked line 14)

ongonOP•3mo ago

it's a very brute force method so I was doing first for loop is word 1 second for loop is word 2 while loop will check if the characters at matching index are the same and then add them to a prefix which will be check to see if its longer than the longest prefix (if there is one from before). if that makes any sense. also I understand its a very brute force method. just noticed my increments for the while loop are in the wrong spot but I feel like there is bigger issues as well.

sidge•3mo ago

What I would do, granted this is coming from someone who hasn’t done this problem in a while, is finding the shortest string in the array, and using that as the length of the second for loop, compare all the strings to the value at that index of the shortest, and if it passes all, add that character to a string or make the string you’re storing a slice to that index, and if not, just return the stored string from the previous index If you sort the string array you can also shave off one iteration from the nested for loop because you already know the 0th index string is the shortest

Vutinberg•3mo ago

Oh I think my brain was overcomplicating this problem as I was writing my explanation

sidge•3mo ago

Though that is totally marginal gains

ongonOP•3mo ago

yea, I don't think my mess of code helped :Despairge:

sidge•3mo ago

Yeah it’s not a crazy problem but it definitely can trip you up if you think too hard

Vutinberg•3mo ago

I was thinking that it was a problem involving any of the strings in the array having potential matching prefixes with any other string, not prefixes that are common with every string in the array

sidge•3mo ago

All you need is a record of the string up until the first for loop index until it fails

Vutinberg•3mo ago

Yeah

sidge•3mo ago

Or ig second for loop depending on how you’re doing it

Vutinberg•3mo ago

-# I have never done leetcode and given everyone's reactions to leetcode I was expecting something more like this

sidge•3mo ago

Leetcode is absolutely all over the place. Some are very easy, and easys are very hard

Vutinberg•3mo ago

By the way is this required to be done in C++ because that really does add extra difficulty for basically no reason. More understanding C++ at that point then understanding the problem itself.

ongonOP•3mo ago

no but I am ironically most comfortable with C++ since its what I used during most of my classes in college.

sidge•3mo ago

Fair enough Does my explanation make sense?

ongonOP•3mo ago

kinda, imma just throw my current code block in here with comments/pseudo code so maybe you could make since of my thinking.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // BRUTE FORCE METHOD???

        // create longestPrefix string and int i variables
        string longestPrefix = "";
        int i = 0;

        // loop through the vector of strings (strs)
        for (i; i < strs.size(); ++i) {
            // set int k to the index of the next string in strs
            int k = i + 1;

            // loop through the strings after the strings at index i
            for (k; k < strs.size(); ++k) {
                // initialize j and l variables to index the characters inside of the 1st and 2nd strings
                int j = 0;
                int l = 0;

                // while the matching index characters for string 1 and 2 are the same
                while (strs[i][j] == strs[k][l]) {
                    // create variables "newPrefix"
                    string newPrefix = "";

                    // add the character to newPrefix
                    newPrefix.push_back(strs[i][j]);

                    // if the new prefix is longer than the longest prefix
                    if (newPrefix.length() > longestPrefix.length()) {
                        // replace longestPrefix with newPrefix
                        longestPrefix = newPrefix;
                    }

                    // if the next index of j or l is longer than the length of their string
                    if (j + 1 > strs[i].length() || l + 1 > strs[k].length()) {
                        // break the loop
                        break;
                    }

                    // increment j and l variables
                    ++j;
                    ++l;
                }
            }
        }
        return prefix;
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // BRUTE FORCE METHOD???

        // create longestPrefix string and int i variables
        string longestPrefix = "";
        int i = 0;

        // loop through the vector of strings (strs)
        for (i; i < strs.size(); ++i) {
            // set int k to the index of the next string in strs
            int k = i + 1;

            // loop through the strings after the strings at index i
            for (k; k < strs.size(); ++k) {
                // initialize j and l variables to index the characters inside of the 1st and 2nd strings
                int j = 0;
                int l = 0;

                // while the matching index characters for string 1 and 2 are the same
                while (strs[i][j] == strs[k][l]) {
                    // create variables "newPrefix"
                    string newPrefix = "";

                    // add the character to newPrefix
                    newPrefix.push_back(strs[i][j]);

                    // if the new prefix is longer than the longest prefix
                    if (newPrefix.length() > longestPrefix.length()) {
                        // replace longestPrefix with newPrefix
                        longestPrefix = newPrefix;
                    }

                    // if the next index of j or l is longer than the length of their string
                    if (j + 1 > strs[i].length() || l + 1 > strs[k].length()) {
                        // break the loop
                        break;
                    }

                    // increment j and l variables
                    ++j;
                    ++l;
                }
            }
        }
        return prefix;
    }
};

sidge•3mo ago

Damn I’m on my phone rn, I’ll check when I’m home

ongonOP•3mo ago

but I do think I understand what you were saying.

sidge•3mo ago

But the third loop is totally unnecessary

Vutinberg•3mo ago

I am looking at this, one of these for loops seems unnecessary (I think sidge's explanation kind of implied that but I am looking more at the code you have then his breakdown) Darnit man typing faster then me :/

ongonOP•3mo ago

lol

Vutinberg•3mo ago

Yeah you basically only need to take the first string, compare that to every other string, Then if you run into the end of the shortest string you can end there. I don't think you even need to find the shortest string, just break the loops if you finish comparing the first string to that? (or break the loop if the first string is gone through)

ongonOP•3mo ago

My question there would be what if there is a prefix longer than the shortest string?

Vutinberg•3mo ago

No based on how this question is worded Since this is a common prefix amongst all strings from my understanding. therefore it can't be a "common" prefix if it's the entirity of the shortest string If this was the problem I was thinking it was, which is the longest common prefix among any possible words in an array (IE you could be tracking multiple potential prefixes to find the longest) that would be different.

ongonOP•3mo ago

oh, that makes sense. I thought we were looking for the longest prefix between two elements in the vector, not every element in the vector. 🤦‍♂️

Vutinberg•3mo ago

Other minor potential bugs in your code, I feel like there is a case where you get an out of bounds but that kind of depends on how ++i works compared to i++ since that may cause slightly different behavior

ongonOP•3mo ago

yea, I noticed that as well. especially with the 2nd for loop since it was always looking for the next index without checking if the next index was even there.

sidge•3mo ago

Is that even possible? They all have to share the prefix oh yeah, important distinction

Vutinberg•3mo ago

I am mostly mentally drafting the behavior which you should really do with a pen and paper (trust me this helps a lot for problems like this, write out the behavior of your loops) But it looks like you will try and go to the last item in the array, and compare it to the last item + 1 in the array given how i and k are working. Which for C++ will throw an error If doing this (which we are not) my first thought would be just compare the first letters of each string, break take strings with similar first letters, Then compare the second letter in those strings with similar first letters, break into strings with similar second letters, (ect) then track how far you get Likely a recursive function in C++

Solution

sidge•3mo ago

so yeah, personally, just to avoid any out of bounds index issues, my process would - sort by shortest string - set a string that you update with the shortest[0]->shortest[i] - iterate through the strings horizontally first - iterate through the array vertically. comparing the strings to shortest at the index of the first loop - this is so, if you can visualize, you can get a vertical "slice" of it all to compare - have a return clause the moment something is not equivalent - at the end of the top level for loop. append that character value to your result string

sidge•3mo ago

take it with a grain of salt, as I am explaning this without writing any code

Vutinberg•3mo ago

(granted at this point you are practically just trying to find the 2 elements most similar to each other)

ongonOP•3mo ago

:NOTED:

sidge•3mo ago

granted you don't actually need to sort, you can just fidn the shortest and leave everything as is, and just iterate with that length as the constraint for your for loop

ongonOP•3mo ago

I used a combination of the shortest word and just iterating to do it from scratch. Here was my result if you guys are interesting in seeing what it looked like completed.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = "";
        string shortWord = "";
        int i;
        int j;
        int k;

        if (strs.size() == 1) {
            prefix = strs[0];
            return prefix;
        }

        for (i; i < strs.size(); ++i) {
            string newWord = strs[i];

            if (shortWord == "") {
                shortWord = newWord;
            }
            else if (newWord < shortWord) {
                shortWord = newWord;
            }
        }

        for (i = 0; i < shortWord.length(); ++i) {
            for (j = 1; j < strs.size(); ++j) {
                if (strs[0][i] != strs[j][i]) {
                    return prefix;
                }
                if (j + 1 == strs.size()) {
                    prefix += strs[0][i];
                }
            }
        }
        return prefix;
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = "";
        string shortWord = "";
        int i;
        int j;
        int k;

        if (strs.size() == 1) {
            prefix = strs[0];
            return prefix;
        }

        for (i; i < strs.size(); ++i) {
            string newWord = strs[i];

            if (shortWord == "") {
                shortWord = newWord;
            }
            else if (newWord < shortWord) {
                shortWord = newWord;
            }
        }

        for (i = 0; i < shortWord.length(); ++i) {
            for (j = 1; j < strs.size(); ++j) {
                if (strs[0][i] != strs[j][i]) {
                    return prefix;
                }
                if (j + 1 == strs.size()) {
                    prefix += strs[0][i];
                }
            }
        }
        return prefix;
    }
};

sidge•3mo ago

Lookin good buddy. Does it pass the leetcode tests and all? Hopefully now that you've got it done, it makes a lot more sense! On one hand, I'm surprised I remembered the solution off the cuff like that, but, on the other hand, once you realize how simple the solution actually is (not to diminish the effort you put in, trust me we've all been there), it kinda sticks and you don't really forget

ongonOP•3mo ago

Yea, I am in a weird spot where it feels like I am “relearning” everything cause while I have my associates degree, allot of the classes were very hand holdy and didn’t require you to completely build something without being told what or how to do it.

Vutinberg•3mo ago

I am not going to lie, looking at these problems I would argue the definitions of what it wants you to do are quite bad. The reality of being a GOOD coder is not being able to translate terrible written requirements, it’s asking whoever gave you those requirements to clarify and ask them questions to build a better understanding of what they want. If interviewers who use Leetcode don’t let you do this, then it is a terrible interview tool as you are basically training coders to make assumptions rather than build clarification.

sidge•3mo ago

yeah leetcode has never been about making industry-quality, like good code it's brainteasers that's all its ever been, and all it ever will be best practices are out of the question

Gaming

Programming

help with a leetcode problem

Did you find this page helpful?