Number of Strings That Appear as Substrings in Word

Difficulty: Easy | Acceptance: 82.50% | Paid: No Topics: Array, String

Given an array of strings patterns and a string word, return the number of strings in patterns that are substrings of word.

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

• Examples
• Constraints
• Brute Force
• Built-in Methods

Examples

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring of "abc".
- "abc" appears as a substring of "abc".
- "bc" appears as a substring of "abc".
- "d" does not appear as a substring of "abc".
Thus, 3 strings in patterns appear as substrings of word.

Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring of "aaaaabbbbb".
- "b" appears as a substring of "aaaaabbbbb".
- "c" does not appear as a substring of "aaaaabbbbb".
Thus, 2 strings in patterns appear as substrings of word.

Example 3:

Input: patterns = ["a","a","a"], word = "ab"
Output: 3
Explanation: All 3 strings in patterns appear as substrings of word.

Constraints

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] and word consist of lowercase English letters.

Brute Force

Intuition We manually check each pattern against the word by iterating through all possible starting positions in the word and comparing characters one by one.

Steps

• Initialize a counter to 0.
• Iterate through each string p in the patterns array.
• For each p, iterate through the word from index 0 to len(word) - len(p).
• At each starting index i in word, check if the substring of word starting at i with length len(p) matches p.
• If a match is found, increment the counter and stop checking the current pattern.
• Return the counter.

class Solution:
    def numOfStrings(self, patterns: list[str], word: str) -> int:
        count = 0
        for p in patterns:
            found = False
            n = len(word)
            m = len(p)
            for i in range(n - m + 1):
                if word[i:i+m] == p:
                    found = True
                    break
            if found:
                count += 1
        return count

Complexity

• Time: O(N * M * L) where N is the number of patterns, M is the length of the word, and L is the average length of a pattern.
• Space: O(1)
• Notes: This approach manually implements the substring check logic without relying on library functions.

Built-in Methods

Intuition Most programming languages provide optimized built-in methods to check if a string contains another string. We can leverage these for cleaner and more concise code.

Steps

• Initialize a counter to 0.
• Iterate through each string p in the patterns array.
• Use the language’s built-in method (e.g., in for Python, contains for Java, find for C++, includes for JavaScript/TypeScript) to check if word contains p.
• If the result is true, increment the counter.
• Return the counter.

class Solution:
    def numOfStrings(self, patterns: list[str], word: str) -> int:
        return sum(1 for p in patterns if p in word)

Complexity

• Time: O(N * M * L) where N is the number of patterns, M is the length of the word, and L is the average length of a pattern. Built-in methods are often highly optimized (e.g., using Boyer-Moore or similar algorithms), but the worst-case complexity remains similar.
• Space: O(1)
• Notes: This is the preferred approach in production due to readability and reliance on standard library optimizations.