Scale Engineer

Number of Strings That Appear as Substrings in Word

Easy
#1793Time: O(N * W * M), where `N` is the number of patterns, `W` is the length of `word`, and `M` is the maximum length of a pattern. For each of the `N` patterns, we scan through `W` possible starting positions in `word`, and for each position, we compare up to `M` characters.Space: O(1), as we only use a few variables to keep track of the count and loop indices, not dependent on the input size.
Data structures
ArrayString

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves manually implementing a substring search algorithm. We iterate through each pattern and then, for each pattern, we iterate through all possible starting positions in the word to see if a match can be found. This is the most fundamental way to solve the problem but also the least efficient.

Algorithm

  • Initialize a counter count to zero.
  • Loop through each pattern string in the patterns array.
  • For each pattern, start a nested loop to check for its presence in word.
  • This inner check involves another loop that iterates from the first character of word up to the last possible starting point for pattern (i.e., word.length() - pattern.length()).
  • At each starting position i in word, we compare the substring of word of length pattern.length() starting at i with the pattern character by character.
  • If a full match is found for the current pattern, we increment count and break the inner loops to move to the next pattern in the patterns array.
  • After checking all patterns, the final count is returned.

Walkthrough

The core idea is to simulate the process of finding a substring without using any library helpers. We take each pattern from the input array and try to find it within the word. To do this, we slide the pattern over the word one character at a time. For each possible starting position in word, we compare the corresponding segment of word with the pattern. If all characters match, we've found a substring. We then increment our counter and move on to the next pattern to avoid overcounting for a single pattern that might appear multiple times.

class Solution {    public int numOfStrings(String[] patterns, String word) {        int count = 0;        for (String pattern : patterns) {            if (isSubstring(word, pattern)) {                count++;            }        }        return count;    }     private boolean isSubstring(String text, String pattern) {        int n = text.length();        int m = pattern.length();        if (m == 0) return true;        if (n < m) return false;         for (int i = 0; i <= n - m; i++) {            int j;            for (j = 0; j < m; j++) {                if (text.charAt(i + j) != pattern.charAt(j)) {                    break;                }            }            if (j == m) {                return true; // Found the pattern            }        }        return false; // Pattern not found    }}

Complexity

Time

O(N * W * M), where `N` is the number of patterns, `W` is the length of `word`, and `M` is the maximum length of a pattern. For each of the `N` patterns, we scan through `W` possible starting positions in `word`, and for each position, we compare up to `M` characters.

Space

O(1), as we only use a few variables to keep track of the count and loop indices, not dependent on the input size.

Trade-offs

Pros

  • Simple to understand the logic from first principles.

  • Doesn't rely on built-in library functions for the core substring search logic.

Cons

  • Inefficient due to the triple nested loop structure, leading to a high time complexity.

  • Re-implements functionality that is already available and highly optimized in standard libraries.

  • More verbose and error-prone than using built-in methods.

Solutions

class Solution {public  int numOfStrings(String[] patterns, String word) {    int ans = 0;    for (String p : patterns) {      if (word.contains(p)) {        ++ans;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem