Filter Words by Stored Prefixes
Problem statement
You are given an array of stored strings, prefixes, and an array of candidate strings, words.
Return every word that starts with at least one stored prefix. Matching is case-sensitive. A word also matches when it equals a prefix.
- Keep matching words in their original order.
- Include each matching word once per occurrence in
words, even if it matches several prefixes. - Duplicate prefixes do not create duplicate results.
- If either array is empty, return an empty array. An empty word cannot match because stored prefixes are nonempty.
Build the prefix structure once, then use it to check all candidate words.
Function
filterByPrefixes(prefixes: String[], words: String[]) → String[]Examples
Example 1
prefixes = ["app","bat","car"]words = ["apple","banana","application","bat","cart","cat"]return = ["apple","application","bat","cart"]apple and application start with app. The other matches are bat and cart, starting with bat and car. Keep their order from words.
Example 2
prefixes = ["A","ab"]words = ["Apple","apple","about","A","ab","AB",""]return = ["Apple","about","A","ab","AB"]Matching is case-sensitive. Apple, A, and AB start with uppercase A. about and ab start with lowercase ab. Lowercase apple and the empty word do not match.
Example 3
prefixes = ["a","ab","a"]words = ["ab","ab","b"]return = ["ab","ab"]Each occurrence of ab is kept once, even though it matches multiple stored prefixes. Duplicate prefixes do not duplicate a result, but duplicate words remain separate occurrences.
Constraints
0 <= prefixes.length <= 50000 <= words.length <= 50001 <= prefixes[i].length <= 400 <= words[i].length <= 40- Every character is an English letter (
a-zorA-Z).