We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Strings That Appear as Substrings in Word

Difficulty: Easy

Problem Description

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word. A substring is a contiguous sequence of characters within a string.

Key Insights

  • A substring can be found using the built-in substring search capabilities of most programming languages.
  • The problem requires counting occurrences, which means duplicates in patterns should be considered.
  • The maximum constraints allow for a straightforward solution without performance concerns due to the relatively small sizes.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of patterns and m is the average length of the patterns.
Space Complexity: O(1), as we're only using a counter variable regardless of input size.

Solution

To solve this problem, we can use a simple loop to iterate through each pattern in the array and check if it is a substring of the given word. We utilize the in operator for substring checking, which is efficient and straightforward.

  1. Initialize a counter to zero.
  2. For each pattern in the patterns list, check if it exists in the word.
  3. If it does, increment the counter.
  4. Return the counter after checking all patterns.

Code Solutions

def countPatterns(patterns, word):
    count = 0
    for pattern in patterns:
        if pattern in word:  # Check if pattern is a substring of word
            count += 1      # Increment count if found
    return count

# Example usage
patterns = ["a", "abc", "bc", "d"]
word = "abc"
print(countPatterns(patterns, word))  # Output: 3
← Back to All Questions