Count Prefixes of a Given String
Easy · Tries · Array · String · Trie
Problem
You are given an array of strings words and a string s, all made of lowercase English letters.
Return how many strings in words are a prefix of s. A prefix is a substring that starts at the first character of s; s is a prefix of itself. Duplicate entries in words are counted separately.
Examples
Input: words = ["p","pl","plan","plane","an"], s = "plant" Output: 3
"p", "pl" and "plan" start "plant"; "plane" does not, and "an" is inside "plant" but not at its start.
Input: words = ["x","x"], s = "xy" Output: 2
Both copies of "x" count.
Input: words = ["longer"], s = "long" Output: 0
A word longer than s cannot be its prefix.
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length, s.length <= 10
- words[i] and s consist of lowercase English letters only
Approaches
- Baseline: compare every word with the start of s — time O(n · |s|), space O(1)
Follow-up
Here the words are prefixes of s. The use cases turn the question around (how many words have s as their prefix, which needs a count on every trie node) and ask for the longest word that starts s instead of the count.
Related problems
Start free on Cariara · Coding problems · System design studio
