algoadvance

You are given an array of strings patterns and a string word. You want to return the number of patterns[i] that appear as a substring in word.

Example

Input:

patterns = ["a", "abc", "bc", "d"]
word = "abc"

Output:

3

Explanation:

• “a” appears in “abc”
• “abc” appears in “abc”
• “bc” appears in “abc”
• “d” does not appear in “abc”

Constraints

• 1 <= patterns.length <= 100
• 1 <= patterns[i].length <= 100
• 1 <= word.length <= 100
• patterns[i] and word contain only lowercase English letters.

Strategy

Given the constraints, a simple and straightforward approach should work fine:

1. Initialize a counter.
2. Loop through each string in patterns.
3. Check if the current pattern appears as a substring in word using the in keyword.
4. If it does, increment the counter.
5. Return the counter value.

Time Complexity

• Checking if a substring is present in a string in Python has an average time complexity of O(m+n) where m is the length of the pattern and n is the length of the word.
• Since we are doing this for each pattern in the array of length p, the overall time complexity would be O(p * (m+n)), but since both m and n as well as p are restricted to fairly small values (no more than 100), this approach is efficient.

Code

Here’s how you can implement the solution:

def numOfStrings(patterns, word):
    count = 0
    for pattern in patterns:
        if pattern in word:
            count += 1
    return count

# Example usage
patterns = ["a", "abc", "bc", "d"]
word = "abc"
print(numOfStrings(patterns, word)) # Output: 3

Explanation

1. We initialize count to 0.
2. We iterate over each pattern in the patterns list.
3. For each pattern, we check if it is a substring of word using the in operation.
4. If the pattern is found in word, we increment the count.
5. Finally, we return the count.

This code efficiently counts the number of patterns that are substrings of the given word.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?