LeetCode 1408 - String Matching in an Array

Difficulty: 🟢 Easy
Topics: Array, String, String Matching

Solution

You included two different problems in one message, and the second problem (LeetCode 1408) appears to replace the first one while repeating the formatting instructions.

I will proceed with LeetCode 1408 - String Matching in an Array.

Problem Understanding

The problem gives us an array of unique strings called words. We need to find every string in this array that appears as a substring of another string in the same array.

A substring is a contiguous sequence of characters within another string. For example, "hero" is a substring of "superhero" because it appears continuously inside the larger string. However, "her" would also be a substring, while something like "hro" would not because the characters are not contiguous.

The input consists of an array words, where each element is a lowercase English string. The output should be a list containing all strings that are substrings of at least one other word in the array. The order of the returned list does not matter.

The constraints are relatively small. The array can contain at most 100 words, and each word has length at most 30. These limits are important because they tell us that even a somewhat inefficient comparison-based approach will still be fast enough. Since the maximum number of pairwise comparisons is only 100 × 100 = 10,000, we do not need advanced string matching algorithms such as KMP or Rabin-Karp to satisfy performance requirements.

There are several edge cases worth identifying early. A word may be a substring of multiple words, but it should only appear once in the answer. Since all input strings are guaranteed to be unique, we do not need to handle duplicate words. Another important case is when no string is a substring of another, in which case the answer should be an empty list. We also must avoid treating a word as a substring of itself, because every string trivially contains itself.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to compare every word with every other word in the array.

For each word words[i], we check every other word words[j]. If i != j and words[i] appears inside words[j], then words[i] is a valid answer. Once we find a match, we can stop checking further words for that particular string and move to the next candidate.

This approach works because it explicitly verifies the definition of the problem. Every possible pair of strings is examined, ensuring that no valid substring relationship is missed.

Although this is technically a brute-force solution, it is efficient enough given the constraints. Since the maximum input size is small, the total work remains manageable.

Key Insight for an Improved Solution

The key observation is that we do not need sophisticated pattern matching because the input size is tiny. The built-in substring operation is already highly optimized, and checking every pair is inexpensive.

Instead of generating all substrings or building complex data structures, we can simply iterate through all word pairs and use the language's built-in substring containment check. This keeps the implementation clean, readable, and fast enough for the problem constraints.

We can make a small optimization by breaking early once a substring match is found for a word, avoiding unnecessary comparisons.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × m²)	O(1)	Compare every pair and check substring manually
Optimal	O(n² × m)	O(1)	Compare every pair using built-in substring search

Here, n is the number of words and m is the average word length. Since word lengths are capped at 30, the practical runtime is very small.

Algorithm Walkthrough

Initialize an empty result list to store valid substring words.
Iterate through each word in the array. Treat the current word as the candidate substring we want to test.
For each candidate word, iterate through all other words in the array.
Skip comparison when the two words are the same object, because a string should not be considered a substring of itself.
Use a substring containment check to determine whether the candidate word appears inside the current comparison word.
If a match is found, append the candidate word to the result list and stop checking further words for this candidate. We stop early because the problem only asks whether it is a substring of at least one other word.
Continue until every word has been processed.
Return the final result list.

Why it works

The algorithm checks every possible pair of distinct words. For each word, it determines whether there exists another word that contains it as a substring. Since every valid comparison is examined exactly once, no substring relationship can be missed. At the same time, self-comparisons are excluded, preventing incorrect matches. Therefore, the algorithm returns exactly the set of words that satisfy the problem condition.

Python Solution

from typing import List

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        result: List[str] = []

        for current_word in words:
            for other_word in words:
                if current_word == other_word:
                    continue

                if current_word in other_word:
                    result.append(current_word)
                    break

        return result

The implementation follows the algorithm directly. We first create an empty result list to store matching words.

The outer loop selects the current word we want to test. The inner loop compares this word against every other word in the array. If the words are identical, we skip the comparison because a word should not match itself.

The key operation is the expression current_word in other_word, which checks whether the candidate word exists as a substring of another word. Once we find a valid match, we append the word to the result and immediately break from the inner loop. This avoids unnecessary work because one match is sufficient.

Finally, the result list is returned.

Go Solution

func stringMatching(words []string) []string {
    result := []string{}

    for i := 0; i < len(words); i++ {
        currentWord := words[i]

        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }

            if contains(words[j], currentWord) {
                result = append(result, currentWord)
                break
            }
        }
    }

    return result
}

func contains(text string, pattern string) bool {
    return len(pattern) <= len(text) &&
        (pattern == text ||
            len(pattern) == 0 ||
            indexOf(text, pattern) != -1)
}

func indexOf(text string, pattern string) int {
    for i := 0; i <= len(text)-len(pattern); i++ {
        match := true

        for j := 0; j < len(pattern); j++ {
            if text[i+j] != pattern[j] {
                match = false
                break
            }
        }

        if match {
            return i
        }
    }

    return -1
}

A more idiomatic Go solution can use the strings.Contains function from the standard library, but the above implementation shows the substring logic explicitly.

The main difference from Python is that Go does not have a built-in in operator for substring checks. Instead, we either implement a helper function manually or use strings.Contains. Go also uses slices for dynamic arrays, so results are accumulated using append.

An even cleaner LeetCode submission would be:

import "strings"

func stringMatching(words []string) []string {
    result := []string{}

    for i := 0; i < len(words); i++ {
        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }

            if strings.Contains(words[j], words[i]) {
                result = append(result, words[i])
                break
            }
        }
    }

    return result
}

Worked Examples

Example 1

Input:

words = ["mass","as","hero","superhero"]

We compare each word against every other word.

Candidate	Compared Against	Substring Match?	Result
`"mass"`	`"as"`	No	`[]`
`"mass"`	`"hero"`	No	`[]`
`"mass"`	`"superhero"`	No	`[]`
`"as"`	`"mass"`	Yes	`["as"]`
`"hero"`	`"superhero"`	Yes	`["as", "hero"]`

Final output:

["as","hero"]

Example 2

Input:

words = ["leetcode","et","code"]

Candidate	Compared Against	Substring Match?	Result
`"leetcode"`	`"et"`	No	`[]`
`"leetcode"`	`"code"`	No	`[]`
`"et"`	`"leetcode"`	Yes	`["et"]`
`"code"`	`"leetcode"`	Yes	`["et", "code"]`

Final output:

["et","code"]

Example 3

Input:

words = ["blue","green","bu"]

Candidate	Compared Against	Substring Match?	Result
`"blue"`	`"green"`	No	`[]`
`"blue"`	`"bu"`	No	`[]`
`"green"`	`"blue"`	No	`[]`
`"green"`	`"bu"`	No	`[]`
`"bu"`	`"blue"`	No	`[]`
`"bu"`	`"green"`	No	`[]`

Final output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² × m)	Compare every pair of words and perform substring search
Space	O(1)	Only a result list is used, excluding output

The time complexity comes from comparing every pair of words. For each pair, substring matching takes proportional time relative to word length. Since the maximum word length is only 30, the algorithm performs efficiently in practice.

The space complexity is constant because no auxiliary data structures proportional to input size are created. The returned result list is excluded from auxiliary space analysis.

Test Cases

solution = Solution()

# Provided examples
assert sorted(solution.stringMatching(
    ["mass", "as", "hero", "superhero"]
)) == ["as", "hero"]  # Basic substring detection

assert sorted(solution.stringMatching(
    ["leetcode", "et", "code"]
)) == ["code", "et"]  # Multiple substring matches

assert solution.stringMatching(
    ["blue", "green", "bu"]
) == []  # No valid substrings

# Single word
assert solution.stringMatching(
    ["abc"]
) == []  # Cannot match against itself

# Multiple nested substrings
assert sorted(solution.stringMatching(
    ["a", "ab", "abc", "abcd"]
)) == ["a", "ab", "abc"]  # Chain of containment

# Substring appears in multiple words
assert solution.stringMatching(
    ["cat", "scatter", "concatenate"]
) == ["cat"]  # One word found in multiple strings

# Similar prefixes but not substrings
assert solution.stringMatching(
    ["abc", "abd", "abe"]
) == []  # Similar beginnings only

# Maximum overlap style case
assert sorted(solution.stringMatching(
    ["x", "xx", "xxx", "xxxx"]
)) == ["x", "xx", "xxx"]  # Nested repeated characters

Test	Why
`["mass","as","hero","superhero"]`	Validates standard substring detection
`["leetcode","et","code"]`	Verifies multiple answers
`["blue","green","bu"]`	Ensures empty result handling
`["abc"]`	Confirms self-matching is excluded
`["a","ab","abc","abcd"]`	Tests nested substring chains
`["cat","scatter","concatenate"]`	Verifies matching across multiple words
`["abc","abd","abe"]`	Ensures prefix similarity is not confused with substring
`["x","xx","xxx","xxxx"]`	Stress test for repeated patterns

Edge Cases

One important edge case is when the input contains only a single word. Since a word cannot be considered a substring of itself, the answer must always be an empty list. The implementation handles this naturally because every self-comparison is skipped.

Another subtle case occurs when one word is a substring of multiple other words. For example, "cat" may appear inside both "scatter" and "concatenate". A careless implementation might append duplicates to the answer. This solution avoids that problem by breaking immediately after the first successful match.

A third important edge case involves words with similar prefixes or suffixes that are not actual substrings. For instance, "abc" and "abd" share a common prefix but neither contains the other. The substring containment check ensures only contiguous exact matches are counted.

Finally, nested containment cases such as ["a", "ab", "abc", "abcd"] can expose bugs where only direct neighbors are checked. Since the implementation compares every pair of words, it correctly identifies all valid substring relationships regardless of depth.