String Matching in an Array
EasyPrompt
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 <= 1001 <= words[i].length <= 30words[i]contains only lowercase English letters.- All the strings of
wordsare 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>namedresultto store the qualifying words. - Get the total number of words,
n. - Use a nested loop structure. The outer loop iterates from
i = 0ton-1. - The inner loop iterates from
j = 0ton-1. - Inside the loops, if
iequalsj,continueto the next iteration. - Check if
words[j].contains(words[i]). - If the condition is true, add
words[i]to theresultset andbreakthe inner loop to proceed to the next word in the outer loop. - Finally, convert the
resultset into aListand 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.
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
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.
Solutions
Solution
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 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.