String Matching in an Array – Explained with Intuition & Visualization

Difficulty: Easy
Topics: Strings, Brute Force, Searching

🧠 Problem Understanding (In Simple Words)

You are given a list of words.

👉 Your task is to find: Which words are contained inside another word in the same list?

In other words:

• If one word appears as a part of another word, include it in the result.

💡 Intuition (How to Think About It)

Think of each word as a pattern.

Now ask: 👉 "Does this pattern exist inside any other word?"

Example:

• "as" is inside "mass"
• "hero" is inside "superhero"

So both should be included.

🔍 Key Idea

For every word:

• Compare it with all other words
• Check: 👉 Is this word a substring of any other word?

If yes → add it to result

🚀 Approach (Step-by-Step)

1. Create an empty result list
2. For each word w1 in the array:
   • Compare it with every other word w2
   • If w1 is found inside w2:
     • Add w1 to result
     • Stop checking further for this word
3. Return the result list

🎯 Visualization Using DrawToCode

This problem becomes much clearer when visualized:

• You can compare two strings visually
• Highlight matching parts (substrings)
• See how smaller words fit inside larger ones

👉 Using DrawToCode, you can:

• Track substring matching step-by-step
• Understand why some matches fail
• Build intuition for string problems

💻 Code (Java Example)

import java.util.*;

public class Main {
    public static 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;
    }
}

⏱️ Complexity Analysis

• Time Complexity: O(n² * m)
  (n = number of words, m = average length of words)

• Space Complexity: O(1) (excluding output list)

🔍 Example Walkthrough

Input:

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

Execution:

• Check "mass" → not inside any other word ❌
• Check "as" → found inside "mass" ✅
• Check "hero" → found inside "superhero" ✅
• Check "superhero" → not inside any other word ❌

👉 Output:

["as", "hero"]

Input:

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

Execution:

• "blue" → no match
• "green" → no match
• "bu" → not found in any word

👉 Output:

[]

🧪 Edge Cases to Consider

• Words with same prefixes but not substrings
• Very short strings
• No matching substrings

🏁 Final Thought

This problem helps you understand:

• String comparison techniques
• Substring detection
• Brute-force pattern matching

👉 Once you visualize string overlaps, these problems become much easier to solve