String Matching in an Array solution and explanation
Google
9 more videos on this problem
String Matching in an Array - Leetcode 1408 - PythonNeetCodeIO · 8:01 · 14K views
String Matching in an Array | Leetcode 1408Techdose · 19:20 · 5K views
String Matching in an Array - Leetcode 1408AlgoWizard · 4:21 · 1K views
How to Solve "1408 String Matching in an Array" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 4:48 · 1K views
Leetcode | 1408. String Matching in an Array | Easy | Java SolutionDeveloper Docs · 7:24 · 976 views
Leetcode | 1408 String Matching in an Array | Java | BruteForce AppraochCakot Coding · 7:16 · 376 views
LeetCode 1408 String Matching in an Array | Easy | String Matching | Asked in GoogleCode Harmony · 12:26 · 149 views
LeetCode 1408 - String Matching in an Array - GoAlpha-Code · 9:39 · 54 views
1408. String Matching in an array | Leetcode daily questionJavAttack · 4:12 · 37 views
LeetCode 1408 | String Matching in an Array | Python Substring Brute-Force | AlgoYogiAlgo Yogi · 9:59 · 28 views
The problem
Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.
A substring is a contiguous sequence of characters within a string
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.
Approach overview
Problem Overview: You are given an array of strings. The task is to return all words that appear as a substring of another word in the same array. For every word, you check whether it exists inside a different word using standard substring or contains operations.
Approach 1: Brute Force Comparison (O(n^2 * m) time, O(1) extra space)
The direct solution compares every word with every other word. Iterate through the array using two nested loops. For each pair (i, j), check if words[j] contains words[i] using built‑in string search such as find(), contains(), or indexOf(). If the substring exists and i != j, add the smaller word to the result. The complexity comes from checking all pairs (n^2) and performing substring search that may scan up to the length of the longer string (m). This approach is simple and works well for the small input sizes typical of array and string interview problems.
Approach 2: Efficient Set-based Comparison (O(n^2 * m) time, O(n) space)
A cleaner implementation uses a HashSet to store all words for quick membership management. Insert all words into a set, then iterate through the list. Temporarily remove the current word so it is not matched with itself. Compare it against the remaining words and check if any string contains it as a substring. The set simplifies duplicate handling and prevents accidental self-matching. While the worst‑case complexity remains O(n^2 * m), the constant factors are slightly lower because each word is handled only once and lookups are O(1). This approach still relies on standard string matching operations provided by the language runtime.
Recommended for interviews: Start with the brute force pairwise comparison. It clearly demonstrates understanding of substring checks and pair iteration. Then mention the set-based refinement to improve code clarity and avoid self-comparisons. Interviewers mainly evaluate whether you recognize that the problem reduces to repeated substring search across the array.
Approach 1: Brute Force Comparison
This approach is straightforward: for each word in the list, check if it is a substring of any other word. We iterate over each pair of words in the array and use string operations to check for substrings.
words = ["mass", "as", "hero", "superhero"]
result = []
for i, word in enumerate(words):
for j, other in enumerate(words):
if i != j and word in other:
result.append(word)
break
print(result)import java.util.ArrayList;
import java.util.List;
public class SubstringTest {
public static void main(String[] args) {
String[] words = {"mass", "as", "hero", "superhero"};
List<String> result = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i != j && words[j].contains(words[i])) {
result.add(words[i]);
break;
}
}
}
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
vector<string> words = {"mass","as","hero","superhero"};
vector<string> result;
for (size_t i = 0; i < words.size(); i++) {
for (size_t j = 0; j < words.size(); j++) {
if (i != j && words[j].find(words[i]) != string::npos) {
result.push_back(words[i]);
break;
}
}
}
for (const string& res : result) {
cout << res << " ";
}
return 0;
}const words = ["mass", "as", "hero", "superhero"];
const result = [];
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words.length; j++) {
if (i !== j && words[j].includes(words[i])) {
result.push(words[i]);
break;
}
}
}
console.log(result);#include <stdio.h>
#include <string.h>
int isSubstring(char *sub, char *str) {
return strstr(str, sub) != NULL;
}
int main() {
char *words[] = {"mass","as","hero","superhero"};
int size = 4;
int found[size];
int k = 0;
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
if (i != j && isSubstring(words[i], words[j])) {
found[k++] = i;
break;
}
}
}
for(int i = 0; i < k; i++) {
printf("%s ", words[found[i]]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
string[] words = { "mass", "as", "hero", "superhero" };
List<string> result = new List<string>();
for (int i = 0; i < words.Length; i++) {
for (int j = 0; j < words.Length; j++) {
if (i != j && words[j].Contains(words[i])) {
result.Add(words[i]);
break;
}
}
}
Console.WriteLine(string.Join(", ", result));
}
}The solution iterates through each word, using Python's in keyword to check for substring existence, and appends matching words to the result list.
Time Complexity: O(n^2 * m)
Space Complexity: O(n)
Approach 2: Efficient Set-based Comparison
This approach creates all possible substrings of each word and stores them in a set, which is then used to quickly check for substring membership against other words.
words = ["mass", "as", "hero", "superhero"]
result = set()
for i, word in enumerate(words):
for j, other in enumerate(words):
if i != j and word in other:
result.add(word)
print(list(result))import java.util.HashSet;
import java.util.Set;
import java.util.List;
import java.util.ArrayList;
public class SubstringEfficient {
public static void main(String[] args) {
String[] words = {"mass", "as", "hero", "superhero"};
Set<String> substrings = new HashSet<>();
List<String> result = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i != j && words[j].contains(words[i])) {
substrings.add(words[i]);
}
}
}
result.addAll(substrings);
System.out.println(result);
}
}#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
int main() {
vector<string> words = {"mass","as","hero","superhero"};
unordered_set<string> substrs;
vector<string> result;
for (size_t i = 0; i < words.size(); ++i) {
for (size_t j = 0; j < words.size(); ++j) {
if (i != j && words[j].find(words[i]) != string::npos) {
substrs.insert(words[i]);
break;
}
}
}
for (const auto& word : substrs) {
result.push_back(word);
}
for (const string& res : result) {
cout << res << " ";
}
return 0;
}const words = ["mass", "as", "hero", "superhero"];
const result = new Set();
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words.length; j++) {
if (i !== j && words[j].includes(words[i])) {
result.add(words[i]);
}
}
}
console.log([...result]);#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isSubstring(char *sub, char *str) {
return strstr(str, sub) != NULL;
}
int main() {
char *words[] = {"mass", "as", "hero", "superhero"};
int size = 4;
bool result[size];
memset(result, false, sizeof(result));
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
if (i != j && isSubstring(words[i], words[j])) {
result[i] = true;
break;
}
}
}
for(int i = 0; i < size; i++) {
if (result[i]) {
printf("%s ", words[i]);
}
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
string[] words = { "mass", "as", "hero", "superhero" };
HashSet<string> substrings = new HashSet<string>();
for (int i = 0; i < words.Length; i++) {
for (int j = 0; j < words.Length; j++) {
if (i != j && words[j].Contains(words[i])) {
substrings.Add(words[i]);
break;
}
}
}
Console.WriteLine(string.Join(", ", substrings));
}
}This Python implementation uses a set to automatically manage duplicates of discovered substrings, collecting results into a set and outputting as a list.
Time Complexity: O(n^2 * m) effectively using set advantages
Space Complexity: O(n)
Approach 3: Brute Force Enumeration
We directly enumerate all strings words[i], and check whether it is a substring of other strings. If it is, we add it to the answer.
The time complexity is O(n^3), and the space complexity is O(n). Where n is the length of the string array.
function stringMatching(words: string[]): string[] {
const ans: string[] = [];
const n = words.length;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (words[j].includes(words[i]) && i !== j) {
ans.push(words[i]);
break;
}
}
}
return ans;
}func stringMatching(words []string) []string {
ans := []string{}
for i, w1 := range words {
for j, w2 := range words {
if i != j && strings.Contains(w2, w1) {
ans = append(ans, w1)
break
}
}
}
return ans
}impl Solution {
pub fn string_matching(words: Vec<String>) -> Vec<String> {
let mut ans = Vec::new();
let n = words.len();
for i in 0..n {
for j in 0..n {
if i != j && words[j].contains(&words[i]) {
ans.push(words[i].clone());
break;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Comparison | Time Complexity: O(n^2 * m) |
| Efficient Set-based Comparison | Time Complexity: O(n^2 * m) effectively using set advantages |
| Brute Force Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n^2 * m) | O(1) | Simple implementation and small input sizes |
| Efficient Set-based Comparison | O(n^2 * m) | O(n) | Cleaner logic, avoids self-comparison and handles duplicates easily |
Frequently asked questions
Is String Matching in an Array easy or hard?
String Matching in an Array is categorized as an Easy problem. The main requirement is understanding substring checks and iterating through all pairs of words. The challenge is recognizing that the problem reduces to simple string containment checks.
String Matching in an Array Python/Java solution
Python solutions typically use the in operator or str.find() to check whether one word appears inside another. Java solutions rely on String.contains() or indexOf(). Both approaches follow the same nested-loop logic and run in O(n^2 * m) time.
How to solve String Matching in an Array in O(n)?
An exact O(n) solution is generally not achievable because each word may need to be compared with multiple other strings. The common optimized approach still performs pairwise checks but uses efficient built‑in substring search, resulting in O(n^2 * m) time in practice.
What is the best approach for String Matching in an Array?
The practical approach is pairwise comparison of every word against the others using a substring check such as contains() or find(). This runs in O(n^2 * m) time where n is the number of words and m is the maximum word length. Many implementations also use a hash set to avoid self-comparison and simplify the logic.
Is String Matching in an Array asked at Google/Amazon/Meta?
Substring detection and array string processing problems frequently appear in interviews at large tech companies. Variants of string matching, substring search, and pattern detection are common screening questions for companies like Amazon and Google.
What data structure is used in String Matching in an Array?
The core operations rely on arrays (or lists) of strings and built-in string search functions. Many implementations also use a HashSet to store the words, allowing quick membership checks and preventing comparisons of a word with itself.
What is the time complexity of String Matching in an Array?
The typical solution runs in O(n^2 * m) time. The algorithm compares each pair of words (n^2 comparisons) and each substring check may scan up to m characters. Space complexity is O(1) for the brute force version or O(n) if a set is used to store the words.