algoadvance

Leetcode 2255. Count Prefixes of a Given String

Problem Statement

The problem you are asked to solve is: Given a list of strings words and a string s, return the number of strings in words that are prefixes of s.

A string word is a prefix of s if s starts with word.

Clarifying Questions

Before we start writing the code, let’s clarify the problem:

  1. Can the words list be empty? Yes, if it is empty, the result should be 0.
  2. Can the string s be empty? Yes, if s is empty, no string can be a prefix of it, so the result should be 0.
  3. What is the range of lengths for words and s? Assume the length of words and the length of any string within it (including s) can be up to 100.
  4. Are there any constraints on the type of characters in words and s? No, they can contain any valid lower-case English letters.

Strategy

  1. Initialize a counter to 0.
  2. Iterate through each string in the words list.
  3. Check if the current string is a prefix of s using the substr method or the compare function.
  4. If it is a prefix, increment the counter.
  5. Return the counter after the loop finishes.

Code

Here is the C++ code implementing the above strategy:

#include <vector>
#include <string>

int countPrefixes(std::vector<std::string>& words, std::string s) {
    int count = 0;
    for (const std::string& word : words) {
        if (s.substr(0, word.size()) == word) {
            count++;
        }
    }
    return count;
}

Time Complexity

The time complexity of this solution can be analyzed as follows:

  1. Let n be the number of strings in words.
  2. Let m be the average length of the strings in words.
  3. The substr method operates in O(m) time, where m is the length of the prefix being checked.
  4. The outer loop runs n times.

Hence, the overall time complexity is O(n * m), where n is the size of the words list, and m is the average length of the strings in words.

This solution is efficient for the given problem constraints.

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