algoadvance

Leetcode 2185. Counting Words With a Given Prefix

Problem Statement

You are given an array of strings words and a string prefix. You need to return the number of strings in words that contain the prefix.

Example:

Input: words = ["pay", "attention", "practice", "attend"], prefix = "at"
Output: 2
Explanation: There are two words that start with "at": "attention" and "attend".

Clarifying Questions

  1. Case Sensitivity:
    • Should the matching be case-sensitive?
    • Assumption: Yes, the matching is case-sensitive unless otherwise specified.
  2. Prefix Definition:
    • Is the prefix guaranteed to be non-empty?
    • Assumption: Yes, the prefix is non-empty.
  3. Input Constraints:
    • What are the constraints on the lengths of the input arrays and strings?
    • Assumption:
      • 1 <= words.length <= 100
      • 1 <= words[i].length, prefix.length <= 100

Strategy

  1. Iterate Through Array:
    • We will iterate through each word in the words array.
  2. Check Prefix:
    • For each word, check if it starts with the given prefix using the std::string member function substr.
  3. Count Matching Words:
    • Maintain a counter to keep track of the number of words that start with the prefix.

Code

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

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

int main() {
    std::vector<std::string> words = {"pay", "attention", "practice", "attend"};
    std::string prefix = "at";
    std::cout << "Number of words with the given prefix: " << countWordsWithPrefix(words, prefix) << std::endl;
    return 0;
}

Time Complexity

This solution is efficient given the constraints provided. If the constraints were larger, optimization techniques such as Trie data structures could be considered.

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