String Matching in an Array Leetcode Solution

The problem String Matching in an Array Leetcode Solution provides us with an array of strings. The problem asks us to find the strings that are substrings of some other string from the input. Just a quick reminder, a substring is nothing but a part of the string remaining after removing characters from both ends. You can also remove 0 characters from both the ends. And the number of removed characters does not need to be the same. So, for a better understanding let us take a look at a few examples.

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

["as","hero"]

Explanation: The output has “as” because it comes in “mass”. Similarly, “hero” is a part of “superhero”. Thus, we simply found the substrings of the inputs that are also input.

words = ["leetcode","et","code"]

["et","code"]

Explanation: This example shows that the substrings can be from the same string. Like here, both the strings in the output are substring of “leetcode”.

Approach for String Matching in an Array Leetcode Solution

The problem asked us to pick out the strings from the input that satisfy a specific condition. The condition is that the string should be a substring of a string that is also in the input. So, we try to simulate this process of finding the strings that are substring of some other string.  The only complication that remains is the implementation. So, we use hashset or unordered map to keep track of strings that will serve as our output. We use two nested loops that checks if the string at ith index is a substring of string at jth index and vice-versa. In C++, we created our own function that checks if the second string is a substring of the first argument. In Java, this can be easily found using contains() function.

Code for String Matching in an Array Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

bool isSubstr(string a, string b){
    int n = a.size(), m = b.size();
    for(int i=0;i<=n-m;i++){
        if(a.substr(i, m) == b)
            return true;
    }
    return false;
}

vector<string> stringMatching(vector<string>& words) {
    unordered_set<string> tmp;
    int n = words.size();
    for(int i=0;i<n-1;i++){
        string curWord = words[i];
        for(int j=i+1;j<n;j++){
            string nextWord = words[j];
            if(isSubstr(curWord, nextWord))
                tmp.insert(nextWord);
            if(isSubstr(nextWord, curWord))
                tmp.insert(curWord);
        }
    }
    return vector<string>(tmp.begin(), tmp.end());
}

int main(){
    vector<string> input({"mass","as","hero","superhero"});
    vector<string> v = stringMatching(input);
    for(auto x: v)
        cout<<x<<" ";
}

hero as

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> stringMatching(String[] words) {
        HashSet<String> tmp = new HashSet<>();
        
        int n = words.length;
        for(int i = 0; i<n-1; i++) {
            String curWord = words[i];
            for(int j = i+1; j<n; j++) {
                String nextWord = words[j];
                if(curWord.contains(nextWord))
                    tmp.add(nextWord);
                if(nextWord.contains(curWord))
                    tmp.add(curWord);
            }
        }
        
        return new ArrayList<String>(tmp);
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String[] words = {"mass","as","hero","superhero"};
    List<String> list = stringMatching(words);
    for(String x: list)
      System.out.print(x+" ");
  }
}

hero as

Complexity Analysis

Time complexity

O(N^2*|S|), because we have used two nested loops that are dependent on the number of input strings. Then the function used to find if the string is a substring of other needs O(|S|) time.

Space Complexity

O(N), in the worst-case whole of the input can be the output. Thus the space complexity is linear.