String Matching in Array LeetCode 1408

LeetCode 1408 String Matching in an Array gives you an array of unique strings. Your task is to return all strings in the array that are substrings of another string in the same array. The result can be returned in any order, and because all input strings are unique, there are no duplicates to worry about in the output.

A string w is a substring of another string s if w appears as a contiguous sequence of characters somewhere within s. For example, "as" is a substring of "mass" because it appears at index 1. The problem asks you to collect all strings that satisfy this containment relationship with respect to at least one other string in the array.

The constraints are generous: the array has at most 100 strings, and each string has at most 30 characters. This means the total character count across all strings is at most 3,000, making even naive O(n^2 * m) approaches entirely feasible within time limits.

The brute force strategy is straightforward: for each string words[i], iterate over every other string words[j] where j != i. If words[i] is a substring of words[j], add words[i] to the result and move on to the next candidate. Once a match is found, there is no need to keep checking other strings — words[i] qualifies, so break out of the inner loop.

Using a set to collect results is not strictly necessary here because all input strings are unique, but it can be a useful guard if you are unsure. Alternatively, once you have confirmed words[i] is a substring of some words[j], simply append words[i] to the result list and break. This avoids any duplicate additions.

The time complexity is O(n^2 * m) where n is the number of strings and m is the maximum string length. The substring check itself takes O(m) in the worst case when using a built-in contains or in operator (which typically uses an efficient algorithm internally). With n = 100 and m = 30, the worst case is about 300,000 operations — trivially fast.

The implementation uses two nested loops. The outer loop iterates over each candidate string words[i]. The inner loop iterates over all other strings words[j], checking j != i to avoid comparing a string against itself. If words[i] is found inside words[j], mark words[i] as a match, break out of the inner loop, and add words[i] to the result.

In Python, the in operator for strings checks substring containment: words[i] in words[j] returns True if words[i] appears anywhere inside words[j]. This is clean and idiomatic. In Java, the String.contains() method performs the same check: words[j].contains(words[i]). Both are O(m) in the underlying implementation.

Use a boolean flag found in the outer loop, or use a break with a for-else pattern in Python. In either language, avoid adding duplicates by breaking immediately after the first match. The result list is returned at the end. No sorting is required unless the problem specifies order.

An alternative approach joins all strings into a single large string with a unique separator character such as "#" that cannot appear in any of the words. The resulting joined string looks like "mass#as#hero#superhero". For each word, you then check if it appears in this joined string more than once — or specifically, at a position other than its own occurrence.

The idea is that if a word appears in the joined string at any index that is not the start of its own segment, then it must be a substring of another word in the array. Counting occurrences is one way to detect this: if word appears more than once in the joined string, it must overlap with another word's segment (since the separator ensures no cross-boundary matches).

This approach has the same O(n * m * total_length) asymptotic complexity as the brute force — no improvement there — but it can be expressed more compactly. The separator is critical: it must be a character that cannot appear in any input word. The "#" character works well for lowercase-letter-only inputs.

Consider words = ["mass", "as", "hero", "superhero"]. We check each string against all others. For "mass": is "mass" in "as"? No. Is "mass" in "hero"? No. Is "mass" in "superhero"? No. "mass" does not qualify. For "as": is "as" in "mass"? Yes — "as" appears at index 1 of "mass". Found! Add "as" to result.

For "hero": is "hero" in "mass"? No. Is "hero" in "as"? No. Is "hero" in "superhero"? Yes — "hero" appears at index 5 of "superhero". Found! Add "hero" to result. For "superhero": is "superhero" in "mass"? No. Is "superhero" in "as"? No. Is "superhero" in "hero"? No. "superhero" does not qualify.

Final result: ["as", "hero"]. Both strings appear as substrings within longer strings in the same array. "mass" and "superhero" do not appear inside any other string, so they are excluded. The order depends on iteration order, which matches input order here.

Python solution: def stringMatching(words): result = []; for i, w in enumerate(words): for j, other in enumerate(words): if i != j and w in other: result.append(w); break; return result. Alternatively as a list comprehension: return [w for w in words if any(w in other for other in words if other != w)]. Both are O(n^2 * m) time and O(n) space for the result.

Java solution: public List<String> stringMatching(String[] words) { 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; } } } return result; }. The contains() method handles the substring check in O(m) per call.

Both solutions have O(n^2 * m) time complexity and O(n) space for the output. The space used by the result list is proportional to the number of qualifying strings, which is at most n. No additional data structures are needed beyond the output list. The key correctness requirement is the i != j guard — without it, every string would trivially match itself.

Longest Common Prefix (LeetCode 14) is a classic string problem that asks for the longest prefix shared by all strings in an array. Like LeetCode 1408, it involves comparing strings against each other in a pairwise or iterative fashion. The vertical scanning approach checks each character position across all strings, similar in spirit to the nested loop substring check here.

Determine if Two Strings Are Close (LeetCode 1657) asks whether two strings can be made equal through a series of allowed operations involving character swaps and frequency remapping. It belongs to the string containment and equivalence family — problems where you analyze the relationship between strings based on their character content rather than positional containment.

Encode and Decode Strings (LeetCode 271) deals with serializing an array of strings into a single string and recovering the original array. This is conceptually related to the concatenation trick in LeetCode 1408, where a separator character is used to join strings and later distinguish them. Shifting Letters II (LeetCode 2381) rounds out the string algorithms family with range-based character transformations.