Problem Description

You are given an array of strings called patterns and a single string called word. Your task is to count how many strings from the patterns array appear as substrings within word.

A substring is defined as a contiguous sequence of characters that appears within another string. For example, "cat" is a substring of "concatenate" because the characters 'c', 'a', 't' appear consecutively in that order.

The solution iterates through each pattern p in the patterns array and checks if it exists as a substring in word using Python's in operator. The expression p in word returns True if p is found as a substring in word, and False otherwise. The sum() function counts the total number of True values (since True equals 1 and False equals 0 in Python), giving us the final count of patterns that are substrings of word.

For example, if patterns = ["a", "abc", "bc", "d"] and word = "abc", the result would be 3 because "a", "abc", and "bc" all appear as substrings in "abc", while "d" does not.

Intuition

The problem asks us to find which patterns appear as substrings in a given word. The most straightforward approach is to check each pattern individually against the word.

Since we need to determine if one string is contained within another, we can leverage Python's built-in substring checking capability using the in operator. This operator efficiently checks if a pattern exists anywhere within the word as a contiguous sequence.

The key insight is that we don't need to track positions or implement complex string matching algorithms. We simply need a yes/no answer for each pattern: "Does this pattern exist in the word?" Each positive match contributes 1 to our count.

By using a generator expression (p in word for p in patterns), we create a sequence of boolean values - True for patterns that exist in the word and False for those that don't. Since Python treats True as 1 and False as 0 in numeric contexts, we can directly sum these boolean values to get our final count. This eliminates the need for explicit counting logic or conditional statements.

This approach is both concise and efficient for the problem's requirements, as it leverages Python's optimized string searching implementation while maintaining clear, readable code.

Solution Approach

The implementation uses a simulation approach where we traverse through each string in the patterns array and check if it exists as a substring in word.

The algorithm follows these steps:

1. Iterate through patterns: We go through each string p in the patterns array one by one.

2. Check substring existence: For each pattern p, we check if it appears as a substring in word using Python's in operator. This operator performs an efficient substring search that returns True if p is found anywhere within word, and False otherwise.

3. Count matches: We use Python's sum() function to count the total number of patterns that exist as substrings. Since the expression p in word evaluates to a boolean value, and Python treats True as 1 and False as 0 in numeric operations, summing these boolean values gives us the exact count we need.

The complete solution is implemented in a single line:

return sum(p in word for p in patterns)

This generator expression (p in word for p in patterns) creates a sequence of boolean values for each pattern. The sum() function then adds up all the True values (counting as 1 each) to produce the final count.

The time complexity is O(n * m) where n is the number of patterns and m is the average length of pattern strings multiplied by the length of word, as each substring check operation takes time proportional to the lengths involved. The space complexity is O(1) as we only maintain a running count without storing additional data structures.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Given:

• patterns = ["ab", "abc", "bc", "d", "c"]
• word = "abc"

Step-by-step execution:

1. Check pattern "ab":

   • Is "ab" in "abc"?
   • Yes! "ab" appears at the beginning of "abc"
   • This evaluates to True (counts as 1)

2. Check pattern "abc":

   • Is "abc" in "abc"?
   • Yes! "abc" matches the entire word
   • This evaluates to True (counts as 1)

3. Check pattern "bc":

   • Is "bc" in "abc"?
   • Yes! "bc" appears at the end of "abc"
   • This evaluates to True (counts as 1)

4. Check pattern "d":

   • Is "d" in "abc"?
   • No! The character "d" doesn't appear anywhere in "abc"
   • This evaluates to False (counts as 0)

5. Check pattern "c":

   • Is "c" in "abc"?
   • Yes! "c" appears as the last character of "abc"
   • This evaluates to True (counts as 1)

Final calculation: The generator expression produces: [True, True, True, False, True]

When we apply sum() to these boolean values:

• sum([True, True, True, False, True]) = 1 + 1 + 1 + 0 + 1 = 4

Therefore, 4 patterns from the array appear as substrings in the word "abc".

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m × k), where n is the number of patterns in the list, m is the length of the word, and k is the average length of each pattern. This is because:

• We iterate through n patterns
• For each pattern, the in operator performs substring matching which takes O(m × k) time in the worst case (checking each position in word as a potential start for the pattern)

The space complexity is O(1) as we only use a constant amount of extra space for the sum operation. The generator expression (p in word for p in patterns) doesn't create an intermediate list but yields values one at a time.

Note: The reference answer simplifies the time complexity to O(n × m) by treating the pattern lengths as part of n or considering them constant, which is a valid simplification when analyzing the dominant factors.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Counting Duplicate Occurrences Instead of Unique Patterns

A common misunderstanding is thinking we need to count how many times each pattern appears in the word, rather than just checking if it exists at least once.

Incorrect approach:

def numOfStrings(self, patterns: List[str], word: str) -> int:
    count = 0
    for pattern in patterns:
        # Wrong: This counts occurrences, not just existence
        count += word.count(pattern)
    return count

Why it's wrong: If patterns = ["a"] and word = "aaa", this would return 3 instead of 1. The problem asks for how many patterns are substrings, not how many times they appear.

Correct approach: Use the boolean check pattern in word which only verifies existence.

2. Handling Empty Patterns

Empty strings are valid substrings of any string in Python. If the patterns array contains empty strings, they should be counted.

Potential issue:

def numOfStrings(self, patterns: List[str], word: str) -> int:
    count = 0
    for pattern in patterns:
        # Some might incorrectly filter out empty patterns
        if pattern and pattern in word:  # Wrong filtering!
            count += 1
    return count

Why it matters: If patterns = ["", "a"] and word = "abc", the result should be 2 (both "" and "a" are substrings), not 1.

Solution: Don't add unnecessary filters. Python's in operator correctly handles empty strings:

"" in "any_string"  # Returns True

3. Case Sensitivity Assumptions

The problem doesn't specify case-insensitive matching, so patterns should match exactly as they appear.

Incorrect assumption:

def numOfStrings(self, patterns: List[str], word: str) -> int:
    word_lower = word.lower()
    return sum(p.lower() in word_lower for p in patterns)

Why it's wrong: If patterns = ["A", "a"] and word = "abc", only "a" should match, giving a count of 1, not 2.

Solution: Stick to exact matching without case conversion unless explicitly required.

4. Counting Duplicate Patterns Multiple Times

If the patterns array contains duplicates, each occurrence should be checked independently.

Example scenario:

• patterns = ["a", "a", "b"] and word = "abc"
• Result should be 3 (both "a"s count separately plus "b")

Incorrect approach:

def numOfStrings(self, patterns: List[str], word: str) -> int:
    # Wrong: Using set removes duplicates
    unique_patterns = set(patterns)
    return sum(p in word for p in unique_patterns)

Correct approach: Process each pattern in the original list without deduplication.