Longest Common Prefix

To loop or not to loop.

Everything old is new again.

When navigating through LeetCode, there a few battles that wage on. Mainly, the “just make it work” vs. “how clean and simple can I make this?”. I struggle with the former when I try t adhere to the latter.

Somewhere along the way, I got it in my head to never use nested loops. I don’t know why. I see it again and again — and it works. And I understand it. So, let a new dawn begin!

For this problem, you are given an array of words, and it is your job to find the longest common of these words. There’s a few ways to attack this:

• Horizontally: compare word1 to word 2, then word 2 to word 3, etc.
• Vertically: Look at all the 1st letters together, if they match, then all the 2nd letters, etc.
• Divide and Conquer: compare common elements in the 1st half of the array, and separately in the 2nd half of the array. Then compare the 1st half results to the 2nd half.

For my solution, I used the vertical path along with my attempt to simplify the work, but it does add an extra variable to the mix, which affects speed. (this is where the “make it work” aspect won out)

The first thing I did was do some quick sudo coding:

// find the shortest string in my array(SMALLEST), since the common prefix can't be bigger than that.
// loop through the SMALLEST word in the array
// compare that to the nth letter in each word as we loop through the entire array
// if it matches, add it to our "answer string"
// if not, pull the brakes and return what we have
// Rinse. Repeat. 

First off, let’s take care of edge cases:
If the length of the array is 1, we can return that solo string.
If the length of my array is 0, or the array is null, we’ll return the default ""

I will define string as an empty string — which I can concatenate on later.
I also want to use the smallest string in my array, because we can’t have anything longer that that, so that’s the best comparison element to use. Quick search and I had my smallest element in the array, that I called smallest .

Here’s where it gets a little wonky with the “for loops”:

• One loop will look at each letter in my smallest word. So if my smallest word is “con”, we will start at smallest[0] aka “c”.

• Inside THAT loop, another loop will cycle through each word in the array, [“j” will serve as the index for each word in out array] and confirm (or not) that the indexed letter in each word is smallest[i](in this case: ”c”).
  If it’s not a match, we return the string:

But if it IS a match, we will take that letter and add it to our string. Did someone say concatenate, woot woot!

CONCATENATION. (i think that’s a word)

Whatever we have at the end, be it an empty string, or a string of letters, we’ll return it:

our finished project.

And the stats weren’t too bad either:

So, sometimes it’s best not to worry about the n(0) vs n(log)values and just get it working. You may surprise yourself. I just need to keep telling myself that you’re usually on the right path, it’s a little tweak or syntax that you’re missing. Sudo code it out. Run through the process out loud. Talk to your rubber duck, and get it up and working, warts and all.

not all heroes wear capes