# 07.01.2025 [1408. String Matching in an Array]

Brute force is accepted.

07.01.2025

1408. String Matching in an Array easy blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/857

Problem TLDR

All substrings #easy

Intuition

Brute force is accepted.

Approach

• we can improve speed by searching for at least 2 matches in the joined words (and speed this up with KMP or Robin-Karp rolling hash)

• careful to not include the word twice

Complexity

• Time complexity: $$O(n^2w^2)$$, w^2 for word1.contains(word2)

• Space complexity: $$O(n)$$

Code

    fun stringMatching(words: Array<String>) = 
        words.filter { w -> words.any { w != it && w in it }}

    pub fn string_matching(words: Vec<String>) -> Vec<String> {
        words.iter().filter(|w| words.iter().any(|w2| 
            *w != w2 && w2.contains(*w))).cloned().collect()
    }

    vector<string> stringMatching(vector<string>& words) {
        vector<string> r;
        for (int i = 0; i < words.size(); ++i)
            for (int j = 0; j < words.size(); ++j)
                if (i != j && words[j].find(words[i]) != string::npos) {
                    r.push_back(words[i]); break;
                }
        return r;
    }