#1967

Easy

LeetCode Problem Workspace

Number of Strings That Appear as Substrings in Word

Count how many strings in an array appear as substrings within a given word by checking each pattern individually.

Problem Statement

You are given an array of strings patterns and a string word. Your task is to return the number of strings from the patterns array that exist as substrings in the word.

A substring is a contiguous sequence of characters within a string. For example, 'abc' is a substring of 'abcd', but 'ac' is not. Solve this by checking each pattern string individually, and count how many of them are substrings of the word.

Examples

Example 1

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

Output: 3

"a" appears as a substring in "abc".
"abc" appears as a substring in "abc".
"bc" appears as a substring in "abc".
"d" does not appear as a substring in "abc". 3 of the strings in patterns appear as a substring in word.

Example 2

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"

Output: 2

"a" appears as a substring in "aaaaabbbbb".
"b" appears as a substring in "aaaaabbbbb".
"c" does not appear as a substring in "aaaaabbbbb". 2 of the strings in patterns appear as a substring in word.

Example 3

Input: patterns = ["a","a","a"], word = "ab"

Output: 3

Each of the patterns appears as a substring in word "ab".

Constraints

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] and word consist of lowercase English letters.

Solution Approach

Naive Approach

Loop through each string in patterns and use the built-in string function in to check if it is a substring of word. This approach works well within the given constraints but could become inefficient for larger inputs.

Optimized Approach with Set

Utilize a set to store substrings that have already been matched. This ensures each pattern is checked only once, and further checks are faster by avoiding redundant operations.

Sliding Window Approach

For larger strings, implement a sliding window technique to efficiently check for substring existence by comparing segments of word with each pattern in patterns. This reduces unnecessary checks and speeds up the process.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used: the naive method has O(n * m) time complexity, where n is the length of patterns and m is the average length of the strings in patterns compared with the length of word. Using a set or sliding window can improve efficiency for larger inputs.

What Interviewers Usually Probe

The candidate is expected to demonstrate an understanding of string matching techniques.
Evaluate if the candidate can handle edge cases where multiple identical patterns exist in the array.
Pay attention to how the candidate chooses their approach in terms of complexity and efficiency.

Common Pitfalls or Variants

Common pitfalls

Failing to check for redundant patterns or using inefficient methods for substring matching.
Not considering edge cases where patterns might be of the same string repeated or very similar.
Overlooking the fact that every pattern should be checked individually without assuming overlap between patterns.

Follow-up variants

Test how the function handles an empty patterns array or an empty word.
Try larger patterns arrays or longer words to see if the solution scales appropriately.
Introduce mixed case inputs to assess how the candidate handles edge cases in substring checking.

FAQ

How do I check if a string is a substring of another string?

You can use the built-in in operator in Python, which checks if a substring exists within a string.

What is the best way to solve the 'Number of Strings That Appear as Substrings in Word' problem?

A simple solution would be to loop through each pattern and check if it's a substring of word. You can optimize this by avoiding redundant checks with a set or using a sliding window technique.

How does the sliding window technique work for substring matching?

A sliding window moves over the string to compare substrings of a fixed size with the target pattern, allowing efficient matching of segments in the word.

How do I handle identical patterns in the 'patterns' array?

You can avoid redundant checks by using a set to store previously matched substrings, or by using a dictionary to track the count of patterns already matched.

What is the time complexity of this problem?

The time complexity depends on the approach you choose: the naive method has O(n * m) complexity, while optimized methods such as sliding window can improve performance.

terminal

Solution

Solution 1: Simulation

Traverse each string $p$ in the array $\textit{patterns}$ and check if it is a substring of $\textit{word}$. If it is, increment the answer by one.

1

2

3

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        return sum(p in word for p in patterns)

Continue Practicing

#1961 check if string is a prefix of array #1980 find unique binary string #1985 find the kth largest integer in the array