LeetCode Entry

1408. String Matching in an Array

07.01.2025 easy 2025 kotlin rust

All substrings

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

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;
    }