algoadvance

Leetcode 2255. Count Prefixes of a Given String

Problem Statement

You are given a list of strings words and a string s. A string is called a prefix of s if it can be obtained by removing some (possibly zero) characters from the end of s.

Return the number of strings in words that are prefixes of s.

Clarifying Questions

1. Input Size: What are the constraints on the number of strings in the list words and the length of the string s?
   • Assume there can be up to 1000 strings in words, and the length of each string and s could be up to 1000 characters.
2. Characters: Are the strings composed of only lowercase English letters?
   • Yes, the strings will only contain lowercase English letters.
3. Prefix Definition: Is the prefix definition straightforward?
   • Yes, a prefix of s means it matches the first part of s exactly.

Strategy

1. Initialization: Initialize a counter to zero to count the number of valid prefix strings in words.

2. Loop Through words: Iterate over each string in words.

3. Check Prefix: For each string, check if it is a prefix of s by using the startsWith method in Java.

4. Update Counter: If it is a prefix, increment the counter.

5. Return the Counter: Once all strings in words are checked, return the counter as the result.

Code

class Solution {
    public int countPrefixes(String[] words, String s) {
        int count = 0;
        
        for (String word : words) {
            if (s.startsWith(word)) {
                count++;
            }
        }
        
        return count;
    }
}

Time Complexity

• Initialization: O(1)
• Loop Through words: O(n) where n is the number of strings in words.
• Check Prefix: The startsWith method is O(m) where m is the length of the prefix being checked.
• Overall Complexity: O(n * m) where:
  • n is the number of strings in words
  • m is the average length of the strings

Given the constraints, this approach will be efficient and handle the maximum input sizes effectively.

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?