1967. Number of Strings That Appear as Substrings in Word

#php #leetcode #algorithms #programming

Difficulty: Easy

Topics: Mid Level, Array, String, Weekly Contest 254

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".

Example 4:

Input: patterns = ["abcd"], word = "abc"
Output: 0

Example 5:

Input: patterns = ["hello"], word = "hello"
Output: 1

Example 6:

Input: patterns = ["x","y","z"], word = "xyz"
Output: 3

Example 7:

Input: patterns = ["p","q","r"], word = "abc"
Output: 0

Example 8:

Input: patterns = ["a","b"], word = "a"
Output: 1

Constraints:

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

Hint:

Deal with each of the patterns individually.
Use the built-in function in the language you are using to find if the pattern exists as a substring in word.

Solution:

We need to count how many strings from the given patterns array appear as substrings within the word string. The solution iterates through each pattern, checks if it exists in word using PHP's built-in str_contains() function, and increments a counter for each match.

Approach

Initialize a counter variable to 0.
Loop through each $pattern in the $patterns array.
For each pattern, use PHP's str_contains($word, $pattern) to check if the pattern is a substring of word.
If the pattern is found, increment the counter.
After processing all patterns, return the counter.

Let's implement this solution in PHP: 1967. Number of Strings That Appear as Substrings in Word

<?php
/**
 * @param String[] $patterns
 * @param String $word
 * @return Integer
 */
function numOfStrings(array $patterns, string $word): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo numOfStrings(["a","abc","bc","d"], "abc") .  "\n";         // Output: 3
echo numOfStrings(["a","b","c"], "aaaaabbbbb") .  "\n";         // Output: 2
echo numOfStrings(["a","a","a"], "ab") .  "\n";                 // Output: 3
echo numOfStrings(["abcd"], "abc") .  "\n";                     // Output: 0
echo numOfStrings(["hello"], "hello") .  "\n";                  // Output: 1
echo numOfStrings(["x","y","z"], "xyz") .  "\n";                // Output: 3
echo numOfStrings(["p","q","r"], "abc") .  "\n";                // Output: 0
echo numOfStrings(["a","b"], "a") .  "\n";                      // Output: 1
?>

Explanation:

Simple iteration: The solution iterates over each pattern in the input array.
Built‑in substring check: PHP's str_contains() function efficiently checks whether a string contains a given substring.
Case sensitivity: Since both patterns and word consist of lowercase letters, case sensitivity is not an issue.
Duplicates handled naturally: Each occurrence in the patterns array is checked independently, so duplicate patterns are counted separately (as required by the problem).
Early exit not needed: Since we must check all patterns, we simply accumulate the result.

Complexity Analysis

Time Complexity: O(n * m) in the worst case, where:
- n = number of patterns (≤ 100)
- m = length of word (≤ 100)
- The actual substring search is handled by PHP's internal implementation, which is generally efficient (typically O(n*m) worst-case, but optimized).
Space Complexity: O(1) – only a single integer counter is used, regardless of input size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!