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.

Description Hints 1 Solution Video 8:01

1408. String Matching in an Array

Easy69.8% acceptance5 companies

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 <= 100
1 <= words[i].length <= 30
words[i] contains only lowercase English letters.
All the strings of words are unique.

Asked at 5 companies

Amazon

Google Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Bruteforce to find if one string is substring of another or use KMP algorithm.

8:01

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution