String Matching in an Array - Practice Coding Problems

String Matching in an Array - Problem

Given an array of string words, return all strings in words that are a substring of another word. You can return the answer in any order.

A substring is a contiguous sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: words = ["mass","as","hero","superhero"]

› Output: ["as","hero"]

💡 Note: "as" is a substring of "mass" and "hero" is a substring of "superhero". Return ["as","hero"].

Example 2 — No Substrings

$ Input: words = ["leetcode","et","code"]

› Output: ["et","code"]

💡 Note: "et" is a substring of "leetcode" and "code" is also a substring of "leetcode".

Example 3 — No Matches

$ Input: words = ["blue","green","red"]

› Output: []

💡 Note: None of the words are substrings of another word, so return empty array.

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 30
words[i] contains only lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of strings to analyze

Substring Check

Find which strings are contained in others

Output Result

Return array of substring matches

Key Takeaway

🎯 Key Insight: A string can only be a substring of another string if it's shorter or equal in length

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is that we need to compare every word with every other word to find substring relationships. The brute force approach works well here since we must check all pairs anyway. Best approach uses nested loops: Time: O(n²×m), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Sort by Length First	O(n²×m)	O(k)	Sort words by length, shorter words can only be substrings of longer ones
Brute Force - Check All Pairs	O(n²×m)	O(k)	For each word, check if it's a substring of any other word

Optimized - Sort by Length First — Algorithm Steps

Sort words by length
For each word, only check against longer words
If found as substring, add to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Length

Arrange words from shortest to longest

Compare Efficiently

Only check shorter words against longer ones

Early Termination

Stop checking once a match is found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char word[100];
    int length;
    int index;
} WordInfo;

int compare(const void* a, const void* b) {
    return ((WordInfo*)a)->length - ((WordInfo*)b)->length;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array
    WordInfo words[100];
    int wordCount = 0;
    char* ptr = line + 1; // Skip '['
    
    while (*ptr && *ptr != ']') {
        while (*ptr == ' ' || *ptr == ',' || *ptr == '"') ptr++;
        if (*ptr == ']') break;
        
        int i = 0;
        while (*ptr && *ptr != '"' && *ptr != ']') {
            words[wordCount].word[i++] = *ptr++;
        }
        words[wordCount].word[i] = 0;
        
        if (strlen(words[wordCount].word) > 0) {
            words[wordCount].length = strlen(words[wordCount].word);
            words[wordCount].index = wordCount;
            wordCount++;
        }
        
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
    }
    
    // Sort by length
    qsort(words, wordCount, sizeof(WordInfo), compare);
    
    // Find substrings
    char result[100][100];
    int resultCount = 0;
    
    for (int i = 0; i < wordCount; i++) {
        for (int j = i + 1; j < wordCount; j++) {
            if (strstr(words[j].word, words[i].word) != NULL) {
                strcpy(result[resultCount++], words[i].word);
                break;
            }
        }
    }
    
    // Output as JSON array
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²×m)

Sorting is O(n log n), but nested loops still dominate with O(n²×m)

⚠ Quadratic Growth

Space Complexity

O(k)

Result array stores k substring matches

✓ Linear Space

28.3K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Sort by Length First — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler