Problem Statement in English

You’re given an array of strings patterns and a string word. Return the count of how many strings in patterns appear as a substring in word.

Approach

We can build a set of all possible substrings of word and then check how many strings in patterns are present in that set. This approach ensures that we efficiently check for the presence of each pattern without repeatedly searching through the string.

And we’re done!

Solution in Python


class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        n = len(word)
        prefixes = set()

        for l in range(n):
            for r in range(l + 1, n + 1):
                prefixes.add(word[l:r])

        res = 0

        for p in patterns:
            if p in prefixes:
                res += 1

        return res

Complexity

  • Time: $O(n^2 + m \cdot k)$
    where $n$ is the length of word, $m$ is the number of patterns, and $k$ is the length of the longest pattern. This is because we generate all possible substrings of word (which takes $O(n^2)$ time) and then check each pattern against these substrings (which takes $O(m \cdot k)$ time).

  • Space: $O(n^2)$
    where $n$ is the length of word. This is the space required to store all the unique substrings of word.

And we are done.