Solving Popular Algorithms: String Matching

If you are a returning reader, welcome back! And if you are a first time reader, welcome! Today, we are going to be taking a look at another popular leet code algorithm: String Matching in an Array.

I actually think this is a great problem for beginners and I wish personally that I had looked at this problem a lot sooner myself. So if you are new to algorithms or even just coding in general, I’d suggest you stick around and we can figure out how to solve this problem together!

I think the mayor needs help with that string!

The Problem

The goal of our string matching problem is, given an array of strings, to return all strings which are substrings of another string in our array.

For example, if we were given this array:

words = ["mass", "as", "hero", "superhero"]

Then, we would want to return the strings “as” and “hero”, as both of those strings are themselves substrings of other words in the array.

To give another example, let’s take a look at this array:

words = ["blue","green","bu"]

So, what would we want our algorithm to return in this case? Well, since blue in not a substring of green or bu, and vice versa, we would just want to return an empty array.

Now that we hopefully understand the problem, let’s get right into solving!

The Solution: An Overview

One thing that I find super helpful when solving problems like this one, is taking the time to write out my thought process for how I think we could solve the problem.

For this problem, I first recognized that one way to solve the problem would be to compare each string in our array to every other string in the array. To accomplish this, we would want to use nested for loops.

Once we have iterated twice through our array, we would then want to check to see if one string includes another string in our array. Then, if the string is included in the other string, we can push it into some final “results” array which will be returned at the end.

Now, we can take our basic idea and begin to translate it into code!

The Solution: Thoughts Translated to Code

strMatching = (words) => {
   let results = []
   
   for (let i = 0; i < words.length-1; i++){
      for (let j = i+1; j < words.length; j++) {
         if (words[i].includes(words[j])) {
            results.push(words[j])
         }
      }
   }
   return results
}

The Solution: Some new things to consider

When I was first solving this algorithm, I really expected the solution above to work. And it does.

Sort of.

While our general idea is correct, if you were to run this code in a repl with our first test case of where words = [“mass”, “as”, “hero”, “superhero”] we would just get “as” as our result.

While close, this is obviously not the result that we want, so what’s the issue?

To figure this out, let’s walk through our algorithm together.

Starting at i = 0 and j = i+1 (aka 1), the first comparison our algorithm will make is to check to see if mass (words[0]) includes as (words[1]). Obviously, it does, so our algorithm will then correctly push “as” into our results array and both i and j will increment.

Now, our algorithm will check to see if as words[1] includes hero words[2]. Of course, it doesn’t, so nothing will be pushed to results and again i and j will increment and we will check to see if hero (words[2]) includes superhero (words[3]). It doesn’t.

So, we can increment again, expect, wait. Our i variable will not increment past words.length-1, so our algorithm will just end here and thus our algorithm will not ever check to see if superhero includes any words in our array.

Now that we understand what’s happening to make our algorithm fail, let’s see if there’s a way to fix this. One simple way to fix our solution is to create an else case that would reverse the scenarios, checking to see if words[j] includes words[i]:

strMatching = (words) => {
   let results = []
   
   for (let i = 0; i < words.length-1; i++){
      for (let j = i+1; j < words.length; j++) {
         if (words[i].includes(words[j])) {
            results.push(words[j])
         } else if (words[j].includes(words[i])) {
            results.push(words[j])
         }
      }
   }
   return results
}

If we try our first test case now, using this solution we will actually pass and return both “as” and “hero”, just like we wanted.

Now that we are getting close, let’s try another test case to see if our algorithm holds up. For this test case, let’s pass in words = [“leetcoder”, “leetcode”, “od”, “hamlet”, “am”].

Using the algorithm above, we would return results = [ ‘leetcode’, ‘od’, ‘od’, ‘am’ ].

Like before, this results array is quite close to what we wanted, however there is a slight problem: the repetition of “od”. So, how do we fix that?

strMatching = (words) => {
   let results = []
   
   for (let i = 0; i < words.length-1; i++){
      for (let j = i+1; j < words.length; j++) {
         if (words[i].includes(words[j]) && !results.includes(words[j])) {
            results.push(words[j])
         } else if (words[j].includes(words[i]) && !results.includes(words[i])) {
            results.push(words[j])
         }
      }
   }
   return results
}

There you have it, our completed solution to this problem! As always, I hope you enjoyed my guide to this algorithm and if you have any questions or suggestions when you try to solve this on your own, please let me know!

Good luck and happy coding!

Kitty got the string!