String Matching in an Array

Easy

#1303Time: 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: 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.

Patterns

String Matching

Data structures

Array String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.HashSet;3import java.util.List;4import java.util.Set;5 6class Solution {7    public List<String> stringMatching(String[] words) {8        Set<String> result = new HashSet<>();9        int n = words.length;10        for (int i = 0; i < n; i++) {11            for (int j = 0; j < n; j++) {12                if (i == j) {13                    continue;14                }15                if (words[j].contains(words[i])) {16                    result.add(words[i]);17                    break; 18                }19            }20        }21        return new ArrayList<>(result);22    }23}

Complexity

Time

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

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.

Trade-offs

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.

We can improve upon the brute-force approach by making a simple observation: if a string s1 is a substring of another string s2, then the length of s1 must be less than or equal to the length of s2. By sorting the input array of words by their lengths in ascending order, we can eliminate unnecessary comparisons. We only need to check if a word is a substring of words that are longer than it.

Algorithm

Sort the words array in ascending order based on the length of the strings.
Initialize an empty List<String> named result.
Iterate through the sorted array with an index i from 0 to n-1.
Start a nested loop with an index j from i+1 to n-1.
Inside the inner loop, check if words[j].contains(words[i]).
If it is a substring, add words[i] to the result list.
break the inner loop, as we have confirmed words[i] is a substring and don't need to check it against other longer words.
After the loops complete, return the result list.

Walkthrough

The first step is to sort the words array based on string length. After sorting, we can iterate through the array from i = 0 to n-1. For each words[i], we only need to check it against subsequent words in the array (words[j] where j > i), as these are guaranteed to be of the same or greater length. If we find that words[i] is a substring of any words[j], we add words[i] to our result list and can immediately break out of the inner loop to start checking the next word, words[i+1]. This avoids duplicate entries in the result list, so we can use a simple List instead of a Set.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Comparator;4import java.util.List;5 6class Solution {7    public List<String> stringMatching(String[] words) {8        Arrays.sort(words, Comparator.comparingInt(String::length));9        10        List<String> result = new ArrayList<>();11        int n = words.length;12        13        for (int i = 0; i < n; i++) {14            for (int j = i + 1; j < n; j++) {15                if (words[j].contains(words[i])) {16                    result.add(words[i]);17                    break;18                }19            }20        }21        22        return result;23    }24}

Complexity

Time

O(N * logN + N^2 * L^2). The sorting step takes O(N * logN). The nested loops and `contains()` check contribute O(N^2 * L^2), which is the dominant term. While the asymptotic complexity is the same as the brute-force approach, this method is faster in practice because it reduces the number of string comparisons by roughly half.

Space

O(N * L) in the worst case for the result list. The space used by the sorting algorithm depends on the implementation; in Java, `Arrays.sort` for objects is a merge sort variant that uses O(N) auxiliary space.

Trade-offs

Pros

More efficient than the naive brute-force approach by eliminating impossible cases.
The logic is a clear and direct improvement.

Cons

The worst-case time complexity remains high and is dominated by the nested loops for string searching.

Solutions

Solution

1class Solution {2public3  List<String> stringMatching(String[] words) {4    List<String> ans = new ArrayList<>();5    int n = words.length;6    for (int i = 0; i < n; ++i) {7      for (int j = 0; j < n; ++j) {8        if (i != j && words[j].contains(words[i])) {9          ans.add(words[i]);10          break;11        }12      }13    }14    return ans;15  }16}

1class Solution {2public:3  vector<string> stringMatching(vector<string> &words) {4    vector<string> ans;5    int n = words.size();6    for (int i = 0; i < n; ++i) {7      for (int j = 0; j < n; ++j) {8        if (i != j && words[j].find(words[i]) != string ::npos) {9          ans.push_back(words[i]);10          break;11        }12      }13    }14    return ans;15  }16};

1class Solution:2    def stringMatching(self, words: List[str]) -> List[str]: ans = [] for i, s in enumerate(words): if any(i != j and s in t for j, t in enumerate(words)): ans . append(s) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem