Number Of Strings That Appear As Substrings In Word - Leetcode Solution

The problem "Number Of Strings That Appear As Substrings In Word" on LeetCode asks us to find the number of strings from a given set of strings that appear as substrings in a given string.

Problem Statement

You are given an array of strings patterns and a string word. Your task is to find the number of strings from patterns that appear as a substring in word.

A substring is a contiguous sequence of characters within a string.

Example

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
Therefore, the answer is 3.

Solution

The solution involves iterating over the patterns array and checking if each string is a substring of the word using String's contains() method.

int count = 0;
for (String pattern : patterns) {
    if (word.contains(pattern)) {
        count++;
    }
}
return count;

The contains() method returns true if the pattern is a substring of the word and false otherwise. If it is true, we increment the count variable. Once we have iterated over all the patterns, we return the count variable.

Complexity Analysis

The solution has a time complexity of O(n * m), where n is the number of patterns and m is the length of the word. This is because we iterate over all the patterns and for each pattern, we check if it is a substring of the word using contains() method, which has a time complexity of O(m).

The space complexity is O(1), as we are not using any additional space apart from the input arrays.

Summary

The problem asks us to find the number of strings from a given set of strings that appear as substrings in a given string. The solution is straightforward and involves iterating over the patterns array and checking if each string is a substring of the word using String's contains() method. The time complexity of the solution is O(n * m), and the space complexity is O(1).

1