2185. Counting Words With a Given Prefix - Explanation

Description

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"

Output: 2

Explanation: The two strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["neetcode","neet","nee","code"], pref = "ne"

Output: 3

Explanation: The three strings that contain "ne" as a prefix are: "neetcode","neet" and "nee".

Constraints:

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        N, res = len(pref), 0

        for w in words:
            if len(w) < len(pref):
                continue
            inc = 1
            for i in range(N):
                if w[i] != pref[i]:
                    inc = 0
                    break
            res += inc

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(1)$

Where $m$ is the number of words and $n$ is the length of the string $pref$ .

2. Built-In Method

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        res = 0
        for w in words:
            res += w.startswith(pref)
        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(1)$

Where $m$ is the number of words and $n$ is the length of the string $pref$ .

3. Trie

class PrefixNode:
    def __init__(self):
        self.children = {}   # a -> PrefixNode
        self.count = 0

class PrefixTree:
    def __init__(self):
        self.root = PrefixNode()

    def add(self, w: str, length: int) -> None:
        cur = self.root
        for i in range(length):
            if w[i] not in cur.children:
                cur.children[w[i]] = PrefixNode()
            cur = cur.children[w[i]]
            cur.count += 1

    def count(self, pref: str) -> int:
        cur = self.root
        for c in pref:
            if c not in cur.children:
                return 0
            cur = cur.children[c]
        return cur.count

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        prefix_tree = PrefixTree()

        for w in words:
            if len(w) >= len(pref):
                prefix_tree.add(w, len(pref))

        return prefix_tree.count(pref)

Time & Space Complexity

Time complexity: $O(m * l + n)$
Space complexity: $O(m * l)$

Where $m$ is the number of words, $n$ is the length of the string $pref$ and $l$ is the maximum length of a word.