String Matching in an Array — Solution in Python, Java & C++
String Matching in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
String Matching in an Array is an easy coding problem on arrays, strings and string matching, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, String Matching
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array words of distinct lowercase strings.
Return every string of words that occurs as a substring (a contiguous run of characters) of some other string of words. List them in the order they appear in words; return an empty list if there are none.
Example 1
Input: words = ["kairo","air","code","od","duel"]
Output: ["air","od"]
Explanation: `"air"` sits inside `"kairo"` and `"od"` inside `"code"`.
Example 2
Input: words = ["bug","hunt","bughunt"]
Output: ["bug","hunt"]
Example 3
Input: words = ["abc","xyz"]
Output: []
Constraints
1 <= words.length <= 1001 <= words[i].length <= 30words[i] contains only lowercase English lettersall the strings of words are unique
Hints for String Matching in an Array
Hint 1
With at most 100 short words, comparing every pair is cheap.
Hint 2
For each word, look for another word (a different index) that contains it.
Hint 3
Stop searching for a word as soon as one container is found, so it is reported only once.
How to solve String Matching in an Array
The limits are tiny, so test every ordered pair (i, j) with i != j and ask whether words[j] contains words[i] using the language's substring search.
Approach
- For each index
iin order: - Scan every
j != i; ifwords[i]is a substring ofwords[j], appendwords[i]to the answer and stop scanning for thisi. - Return the answer.
Why it works
A word belongs to the answer exactly when some other word contains it, which is what the inner scan checks. Breaking after the first container keeps each word at most once, and the outer loop runs in input order.
Complexity
- Time —
O(n² · L²) worst case with naive substring search (L ≤ 30) - Space —
O(1) besides the output
Pitfalls
- Skip
j == i: every word contains itself. - Report a word once even if several words contain it.
- Only a longer (or equal-length, impossible here since words are distinct) word can contain another — an optional speed-up, not a requirement.
Reference solution
Python
from typing import List
def stringMatching(words: List[str]) -> List[str]:
res = []
for i, w in enumerate(words):
if any(i != j and w in x for j, x in enumerate(words)):
res.append(w)
return resJava
public static String[] stringMatching(String[] words) {
List<String> res = 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])) {
res.add(words[i]);
break;
}
}
}
return res.toArray(new String[0]);
}C++
vector<string> stringMatching(vector<string>& words) {
vector<string> res;
int n = words.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && words[j].find(words[i]) != string::npos) {
res.push_back(words[i]);
break;
}
}
}
return res;
}JavaScript
var stringMatching = function(words) {
var res = [];
for (var i = 0; i < words.length; i++) {
for (var j = 0; j < words.length; j++) {
if (i !== j && words[j].indexOf(words[i]) >= 0) {
res.push(words[i]);
break;
}
}
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.