{x}
blog image

Number of Strings That Appear as Substrings in Word

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.

 

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "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
Explanation:
- "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
Explanation: 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 Explanation:

This problem asks to count how many strings from a given array patterns are substrings of a given string word. The most straightforward approach is to iterate through each string in patterns and check if it exists as a substring within word.

Approach:

  1. Iteration: We iterate through each string p in the patterns array.
  2. Substring Check: For each p, we check if it's a substring of word. Most programming languages provide built-in functions for this (e.g., contains in Python, includes in JavaScript, find in C++, Contains in Go, etc.). These functions typically have a time complexity of O(m*n) in the worst case where 'm' is the length of the word and 'n' is the length of the pattern.
  3. Counting: If p is a substring of word, we increment a counter.
  4. Return Value: Finally, we return the counter, which represents the total number of strings from patterns that are substrings of word.

Time and Space Complexity Analysis:

  • Time Complexity: The outer loop iterates through each string in patterns (length n). The substring check within the loop has a time complexity of O(m) in the worst case (where m is the length of word). Therefore, the overall time complexity is O(n*m).

  • Space Complexity: The algorithm uses a constant amount of extra space to store the counter and does not depend on the input sizes. Thus, the space complexity is O(1).

Code Implementation (with explanations):

The provided code snippets demonstrate this approach in several programming languages. The core logic remains the same across all languages: iterate, check for substring, and count. Let's examine the Python example in more detail:

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

This Python code utilizes a concise list comprehension within the sum function. Let's break it down:

  • (p in word for p in patterns): This is a generator expression. It iterates through each string p in patterns. For each p, the expression p in word evaluates to True if p is a substring of word, and False otherwise. This creates an iterator yielding a sequence of booleans.

  • sum(...): The sum() function sums the boolean values, treating True as 1 and False as 0. This efficiently counts the number of strings that are substrings.

The other language examples use similar logic, though the syntax for the substring check and iteration might vary slightly. However, the underlying algorithmic approach remains consistent.