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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Strings That Appear as Substrings in Word

Number: 2099

Difficulty: Easy

Paid? No

Companies: Uber

Problem Description

Given an array of strings called patterns and a string called word, determine how many strings in patterns exist as a contiguous substring within word.

Key Insights

  • Iterate over each string in the patterns array.
  • For each pattern, check if it exists as a substring in word.
  • Count each occurrence even if duplicate patterns appear.
  • The constraints ensure that even a simple approach is efficient.

Space and Time Complexity

Time Complexity: O(n * m * k) in the worst-case scenario, where n is the number of patterns, m is the length of word, and k is the average length of a pattern. Given the constraints, this is efficient. Space Complexity: O(1) additional space, aside from the input storage.

Solution

The solution involves iterating through each string in the patterns array and using a built-in substring search (e.g., the "in" operator in Python, indexOf in JavaScript, etc.) to check if the pattern is found in word. Each match increments a counter, which is returned as the final answer. This approach avoids extra data structures, keeping the implementation straightforward and efficient.

Code Solutions

# Function to count the number of patterns that appear as substrings in the word
def numOfStrings(patterns, word):
    count = 0  # Initialize counter for matching patterns
    for pattern in patterns:
        # If the pattern is found in word, increment the count
        if pattern in word:
            count += 1
    return count

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