String Matching in an Array

EASY

Description

Given an array of string words, return all strings in words that are a substring of another word. You can return the answer in any order.

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string of words is substring of another string.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] contains only lowercase English letters.
All the strings of words are unique.

Approaches

Checkout 2 different approaches to solve String Matching in an Array. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

The most straightforward approach is to compare every string in the array with every other string. We can use nested loops to achieve this. For each pair of distinct strings, word1 and word2, we check if word1 is a substring of word2.

Algorithm

Initialize an empty Set<String> named result to store the qualifying words.
Get the total number of words, n.
Use a nested loop structure. The outer loop iterates from i = 0 to n-1.
The inner loop iterates from j = 0 to n-1.
Inside the loops, if i equals j, continue to the next iteration.
Check if words[j].contains(words[i]).
If the condition is true, add words[i] to the result set and break the inner loop to proceed to the next word in the outer loop.
Finally, convert the result set into a List and return it.

We iterate through the words array with an outer loop (let's say for word_i) and an inner loop (for word_j). To ensure we are checking against a different word, we skip the case where the indices i and j are the same. Inside the inner loop, we use the contains() method to check if words[i] is a substring of words[j]. If it is, we've found a match. To avoid adding the same word multiple times to our result (e.g., 'a' could be a substring of 'ba' and 'ca'), we use a Set to store the results. After checking all pairs, we convert the set to a list.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> stringMatching(String[] words) {
        Set<String> result = new HashSet<>();
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                if (words[j].contains(words[i])) {
                    result.add(words[i]);
                    break; 
                }
            }
        }
        return new ArrayList<>(result);
    }
}

Complexity Analysis

Time Complexity: O(N^2 * L^2), where N is the number of strings in the `words` array and L is the maximum length of a string. The nested loops run in O(N^2), and the `String.contains()` method can take up to O(L_i * L_j) in the worst case, which simplifies to O(L^2).Space Complexity: O(K * L), where K is the number of strings that are substrings of others. In the worst case, this can be O(N * L) to store the results in the set, where N is the total number of words and L is the max length of a word.

Pros and Cons

Pros:

Simple to conceptualize and implement.
Works correctly for the given constraints.

Cons:

Inefficient due to the number of comparisons.
Performs many redundant checks, such as checking if a longer string is a substring of a shorter one.

Code Solutions

Checking out 3 solutions in different languages for String Matching in an Array. Click on different languages to view the code.

class Solution {
public
  List<String> stringMatching(String[] words) {
    List<String> ans = new ArrayList<>();
    int n = words.length;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j && words[j].contains(words[i])) {
          ans.add(words[i]);
          break;
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for String Matching in an Array

Patterns:

String Matching

Data Structures:

ArrayString