1967. Number of Strings That Appear as Substrings in Word

Array
String
String Matching

TIME

O(n |word| |pattern|)

SPACE

O(1)

Intuition

Just count how many patterns occur as a substring of word. With everything bounded by 100, a direct substring check per pattern is more than fast enough.

Approach

For each pattern, test whether it is a substring of word (p in word / word.contains(p)).
Count the ones that are.

Complexity

Time: O(n · |word| · |pattern|) worst case for naive substring search; trivially small here
Space: O(1)

Edge Cases

Duplicate patterns each count separately (Example 3)
Pattern longer than word → never a substring
Single-character patterns → simple membership check

Code

from typing import List


class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        """
        1967. Number of Strings That Appear as Substrings in Word
        Time: O(n * |word| * |pattern|)
        Space: O(1)
        """
        return sum(1 for p in patterns if p in word)

/**
 * 1967. Number of Strings That Appear as Substrings in Word
 * Time: O(n * |word| * |pattern|)
 * Space: O(1)
 */
class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int count = 0;
        for (String p : patterns) {
            if (word.contains(p)) {
                count++;
            }
        }
        return count;
    }
}