Number of Strings That Appear as Substrings in Word - Solution & Explanation

Problem Overview: You are given an array patterns and a string word. The task is to count how many strings in patterns appear as a substring inside word. Each pattern is checked independently, and duplicates in the array are counted separately if they match.

This problem is mainly about efficient substring detection using basic string operations. Since the constraints are small, a direct check works well and keeps the implementation clean.

Approach 1: Simple String Contains Check (O(p * n) time, O(1) space)

The most straightforward solution iterates through every string in patterns and checks whether it appears inside word. Most languages provide a built-in substring search such as word.contains(pattern), pattern in word, or indexOf(). Each check scans the target string and determines whether the pattern exists.

The algorithm is simple: iterate over the array of patterns, perform a substring search against word, and increment a counter when a match is found. If there are p patterns and the length of word is n, each search costs up to O(n), resulting in O(p * n) total time. Space usage stays O(1) since no additional data structures are required.

This approach is usually the best choice. Built‑in string search functions are highly optimized and the implementation takes only a few lines.

Approach 2: Pattern Matching with Regular Expressions (O(p * n) time, O(1) space)

Another option uses regular expressions to check if each pattern occurs inside the word. For each string in patterns, compile or construct a regex pattern and test it against word. If the expression matches, the pattern exists as a substring.

The core logic is similar to the previous approach but relies on regex engines for pattern matching. This can be useful in languages like Python or JavaScript where regex matching is concise. However, regex introduces additional overhead and offers no real advantage for simple substring checks.

Time complexity remains O(p * n) because each regex evaluation scans the word. Space complexity stays O(1) since no extra storage proportional to input size is needed.

Recommended for interviews: The simple substring check is what most interviewers expect. It shows you understand how to iterate through the input and leverage efficient built-in string operations. Regex works but is rarely necessary for this problem and can appear overengineered for an Easy-level task.