Number of Strings That Appear as Substrings in Word

Easy

Asked by:

11 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you provide the constraints for the lengths of `patterns` and `word`? Are they bounded by a specific maximum length?
Are the strings in `patterns` guaranteed to be non-empty? What should I return if `patterns` contains an empty string?
Is the comparison case-sensitive? Should I treat 'abc' and 'Abc' as the same or different substrings?
If a pattern appears multiple times as a substring in `word`, should I count each occurrence separately, or only count it once?
What is the expected return value if the `patterns` array is empty?

Brute Force Solution

Approach

The brute force approach to find substrings involves checking every possible small word to see if it is inside the larger word. It’s like manually searching through a book to see if you can find each of the smaller words somewhere within the bigger word.

Here's how the algorithm would work step-by-step:

Start with the first small word.
Check if this small word exists at the very beginning of the big word.
If not, check if it exists starting from the second letter of the big word, then the third, and so on.
Continue doing this until you have checked every possible starting position in the big word.
If you find a match, remember that you found one.
Move to the next small word and repeat the whole process of checking it against every possible starting position in the big word.
Keep doing this for all the small words. Count how many small words you found inside the big word in total.

Code Implementation

def number_of_strings_that_appear_as_substrings_in_word(patterns, word):
    number_of_matches = 0
    for pattern in patterns:
        # Iterate through each pattern in the list of patterns
        for index in range(len(word) - len(pattern) + 1):

            if word[index:index + len(pattern)] == pattern:
                # Check if the pattern matches the substring in the main word
                number_of_matches += 1
                # No need to keep checking this pattern
                break

    return number_of_matches

Big(O) Analysis

Time Complexity

O(m*n*k) – Let m be the number of small words, n be the length of the large word 'word', and k be the average length of the small words in 'patterns'. The outer loop iterates through each of the m small words. For each small word, the algorithm iterates through the large word 'word' almost n times (checking for a substring at each position). The substring check itself takes O(k) time in the worst case, where k is the length of the small word being checked. Therefore, the overall time complexity is O(m*n*k).

Space Complexity

O(1) – The provided solution iterates through the `small words` and the `big word` character by character, performing comparisons. It only uses a counter to keep track of the number of small words found as substrings. Therefore, the algorithm requires a constant amount of extra space, irrespective of the lengths of the input strings. This results in O(1) space complexity.

Optimal Solution

Approach

The best way to solve this is to directly check if each small string is a part of the big string. We can do this without looking at every single possible starting position in the big string. We will iterate through the small strings and use a built-in function to verify if a string is contained in another.

Here's how the algorithm would work step-by-step:

Start with a counter set to zero to keep track of how many small strings are found in the big string.
Take the first small string from the list of small strings.
Check if this small string exists anywhere inside the big string. Use the contains function for this.
If the small string is found in the big string, increase the counter by one.
Repeat this process for each of the small strings in the list.
Once all small strings have been checked, the counter will hold the number of small strings that are present in the big string.
Return the final count.

Code Implementation

def number_of_strings_that_appear_as_substrings_in_word(small_strings, big_string):
    number_of_small_strings_found = 0

    # We iterate through each small string to check if its a substring
    for current_small_string in small_strings:

        # Check if the current small string is a substring of the big string
        if current_small_string in big_string:

            number_of_small_strings_found += 1

    # Return the total count of small strings found in the big string
    return number_of_small_strings_found

Big(O) Analysis

Time Complexity

O(n * m) – Let n be the number of small strings and m be the length of the word (big string). The algorithm iterates through each of the n small strings. For each small string, it uses the 'contains' function which typically has a time complexity proportional to the length of the word (m) because, in the worst case, it needs to compare the small string against all possible substrings of length small_string.length within the word. Therefore, the overall time complexity is O(n * m).

Space Complexity

O(1) – The algorithm uses a counter to track the number of small strings found, which is a constant space variable. The 'contains' function called internally by most languages does not fundamentally allocate a substantial amount of new memory that scales with the input sizes of the small strings or the large word. Therefore, the auxiliary space used by the algorithm is constant and does not depend on the input size.

Edge Cases

Case	How to Handle
patterns is null or empty	Return 0, as no patterns can be substrings of word.
word is null or empty	Return 0, as no substrings can exist in an empty word.
patterns contains an empty string	Count occurrences of empty string as a substring of word, which means it appears 1 time.
word is a very long string (e.g., 10^5 characters)	Ensure algorithm scales linearly or better, avoiding quadratic or worse time complexity.
patterns contains duplicate strings	Count each unique string only once, even if it appears multiple times in patterns.
patterns contains strings longer than word	These strings can never be substrings, so ignore them.
All patterns are identical and substrings of word	Count the pattern only once.
No patterns are substrings of word	Return 0, indicating no matches found.

patterns is null or empty

How to Handle:

Return 0, as no patterns can be substrings of word.

word is null or empty

How to Handle:

Return 0, as no substrings can exist in an empty word.

patterns contains an empty string

How to Handle:

Count occurrences of empty string as a substring of word, which means it appears 1 time.

word is a very long string (e.g., 10^5 characters)

How to Handle:

Ensure algorithm scales linearly or better, avoiding quadratic or worse time complexity.

patterns contains duplicate strings

How to Handle:

Count each unique string only once, even if it appears multiple times in patterns.

patterns contains strings longer than word

How to Handle:

These strings can never be substrings, so ignore them.

All patterns are identical and substrings of word

How to Handle:

Count the pattern only once.

No patterns are substrings of word

How to Handle:

Return 0, indicating no matches found.