2185. Counting Words With a Given Prefix - Detailed Explanation

Problem Statement

You are given an array of strings words and a string pref. Your task is to count how many strings in words have pref as a prefix. A string pref is considered a prefix of a string word if word starts with pref.

Examples:

1. Example 1:

   • Input: words = ["pay", "attention", "practice", "attend"], pref = "at"
   • Output: 2
   • Explanation: Among the words, "attention" and "attend" start with "at".

2. Example 2:

   • Input: words = ["leetcode", "win", "loops", "success"], pref = "code"
   • Output: 0
   • Explanation: No word starts with "code".

3. Example 3:

   • Input: words = ["apple", "app", "application"], pref = "app"
   • Output: 3
   • Explanation: All the words start with "app".

Constraints:

• The array words can have a reasonable number of strings.
• Each string in words and the prefix pref contain only lowercase English letters.
• The length of pref is at least 1.

Hints Before Solving

• Hint 1: Think about how you can check if one string starts with another.
• Hint 2: For each word in the list, you only need to check the beginning segment (of length equal to pref) to determine if it matches pref.
• Hint 3: Consider what built-in string methods your programming language offers for prefix checking.

Approaches to Solve the Problem

Approach 1: Brute Force Iteration

Explanation:

• Idea:
  Iterate through each word in the words array and check if the word starts with pref using string comparison.

• Steps:

  1. Initialize a counter to 0.
  2. For each word in words, check if the first len(pref) characters of the word equal pref.
  3. If they match, increment the counter.
  4. Return the counter after processing all words.

• Visual Walkthrough:
  For words = ["apple", "app", "application"] and pref = "app":

  • Check "apple" → first 3 letters are "app" → count becomes 1.
  • Check "app" → it exactly matches "app" → count becomes 2.
  • Check "application" → first 3 letters are "app" → count becomes 3.

Complexity:

• Time Complexity: O(n * m), where n is the number of words and m is the length of the prefix.
• Space Complexity: O(1) extra space.

Approach 2: Using a Trie (Prefix Tree)

Explanation:

• Idea:
  Build a Trie from the words in the array. Once the Trie is built, traverse it using the characters of pref to reach the corresponding node, then count all words that have that node as a prefix.

• Steps:

  1. Insert all words into the Trie.
  2. Traverse the Trie using pref. If at any point the path does not exist, return 0.
  3. Once at the node corresponding to the end of pref, count the number of words that have this prefix (this can be done by storing a count at each node during insertion).

• Visual Walkthrough:
  Given words = ["pay", "attention", "practice", "attend"] and pref = "at", the Trie would have a branch starting with 'a' → 't' that records a count of 2 (from "attention" and "attend").

Complexity:

• Time Complexity:
  • Building the Trie: O(total length of all words).
  • Querying the prefix: O(m) where m is the length of pref.
• Space Complexity: O(total length of all words) for storing the Trie.

Note: While the Trie approach is efficient for multiple prefix queries, it might be more complex to implement if you only need to answer a single query.

Code Implementations

Python Implementation (Brute Force Approach)