algoadvance

Leetcode 1967. Number of Strings That Appear as Substrings in Word

Problem Statement

Given an array of strings patterns and a string word, return the number of strings in patterns that appear as substrings in word.

Clarifying Questions

1. What is the maximum length for the word and for each string in patterns?
   • Suppose the length of the word can be up to (10^3) and the length of each pattern can be up to (100).
2. Can the strings in patterns be empty?
   • No, each string in patterns will be non-empty.
3. Are the strings case-sensitive?
   • Yes, strings are case-sensitive.
4. Can patterns contain duplicate strings?
   • Yes, it can contain duplicates.

Strategy

1. Iterate Over Patterns: Iterate over each string in patterns.
2. Check Substring: For each string, check if it appears as a substring in word.
3. Count Matches: Increment a counter for each pattern that appears as a substring in word.
4. Return Result: Return the counter.

Code

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    int numOfStrings(std::vector<std::string>& patterns, std::string word) {
        int count = 0;
        for (const std::string& pattern : patterns) {
            if (word.find(pattern) != std::string::npos) {
                count++;
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    std::vector<std::string> patterns = {"a", "abc", "bc", "d"};
    std::string word = "abc";
    std::cout << sol.numOfStrings(patterns, word) << std::endl;  // Output: 3
    return 0;
}

Time Complexity

• Finding Substring: Checking if one string is a substring of another can be done in (O(n \cdot m)) time in the worst case (n is the length of word and m is the length of pattern) using the find method in C++ STL.
• Total Complexity: Since we do this for each pattern, the overall time complexity is (O(k \cdot n \cdot m)) where k is the number of patterns, n is the length of word, and m is the maximum length of any pattern.

Conclusion

This solution iterates through each pattern and checks if it exists in the word by leveraging the find method from the C++ STL, making it straightforward and easily understandable.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?