algoadvance

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

Problem Statement

You are given an array of strings patterns and a string word. You need to determine how many strings in patterns appear as substrings in word.

Return the number of strings in patterns that appear as substrings in word.

Example:

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

Clarifying Questions

1. What is the length constraint for the patterns array and the word string?
2. Are there any specific characters allowed or disallowed in patterns and word?
3. Should the substring matching be case-sensitive?

Assumptions:

• The sum of the length of all strings in patterns is <= 10^4.
• Characters can be any valid ASCII characters.
• Substring matching is case-sensitive.

Strategy

1. Loop through each pattern in patterns.
2. Check if each pattern is a substring in word.
3. Keep a count of how many patterns are substrings in word.
4. Return the count.

To determine if one string is a substring of another, we can use the contains method of the String class in Java.

Code

import java.util.List;

public class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int count = 0;
        for (String pattern : patterns) {
            if (word.contains(pattern)) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] patterns = {"a","abc","bc","d"};
        String word = "abc";
        System.out.println(sol.numOfStrings(patterns, word)); // Output: 3
    }
}

Time Complexity

• Time Complexity: O(n * m)
  • n: Number of patterns in patterns
  • m: Average length of patterns
  • The contains method in Java is O(m) where m is the length of the substring to be matched in the worst case. Given that the sum of the length of all strings in patterns is <= 10^4, this approach is efficient for competitive programming.
• Space Complexity: O(1)
  • We only use a fixed amount of extra space for the counter and no additional data structures.

This solution should efficiently solve the problem within the given constraints.

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?