Camelcase Matching
Medium · Tries · Array · Two Pointers · String · Trie · String Matching
Problem
You are given an array of strings queries and a string pattern.
A query matches the pattern if you can insert zero or more lowercase letters anywhere into pattern to make it equal to the query. You may not insert uppercase letters, and you may not delete or change any character of the pattern.
Return a list of booleans answer where answer[i] is true when queries[i] matches pattern.
Examples
Input: queries = ["HashMap","HashTable","HighMark","HashMapKey"], pattern = "HM" Output: [true,false,true,false]
"HashTable" has an extra capital T and "HashMapKey" an extra K.
Input: queries = ["goodDay","goDay","gDay"], pattern = "goDay" Output: [true,true,false]
"goodDay" inserts "od". "gDay" is missing the pattern's o.
Input: queries = ["FooBar","FootBall","FrameBuffer"], pattern = "FoBa" Output: [true,true,false]
"FootBall" inserts "t" and "l"; "FrameBuffer" has no "o" after F.
Constraints
- 1 <= len(pattern), len(queries) <= 100
- 1 <= len(queries[i]) <= 100
- queries[i] and pattern consist of English letters
Approaches
- Baseline: table over query and pattern positions — time O(total length · len(pattern)), space O(len(pattern))
Follow-up
With 100 queries a two-pointer scan per query is all that is needed; a trie over the queries would only help with many patterns against the same query set. The use cases forgive one extra capital, and search the way code editors do, by prefixes of each hump.
Related problems
Start free on Cariara · Coding problems · System design studio
