Is Camelcase Matching easy or hard?

Camelcase Matching is generally rated Medium difficulty. The logic is straightforward once you recognize that uppercase letters must match exactly while lowercase letters can be skipped. The challenge lies in implementing the conditions cleanly during the two-pointer traversal.

Camelcase Matching Python/Java solution

In Python or Java, the typical implementation uses two pointers to iterate through the query and pattern strings. For each query, advance both pointers on matches, skip lowercase mismatches, and reject unmatched uppercase letters. The logic is identical across languages and runs in O(q * n) time.

How to solve Camelcase Matching in O(n)?

Process each query with a two-pointer scan against the pattern. Iterate through the query characters and compare them with the pattern pointer. Skip lowercase mismatches but reject any unmatched uppercase characters. Each query takes O(n) time because every character is examined once.

What is the best approach for Camelcase Matching?

The two-pointer technique is the best approach. You scan the query and pattern simultaneously, advancing the pattern pointer only when characters match. Lowercase characters in the query can be skipped, but any unmatched uppercase letter invalidates the match. This approach runs in O(q * n) time with O(1) extra space.

Is Camelcase Matching asked at Google/Amazon/Meta?

Camelcase Matching represents a common string pattern-matching problem similar to questions asked at companies like Google, Amazon, and Meta. It tests careful string traversal, handling uppercase constraints, and writing clean validation logic using pointers.

What data structure is used in Camelcase Matching?

The problem mainly relies on string traversal and pointer manipulation rather than complex data structures. The standard solution uses two pointers over strings. Conceptually, the queries can be viewed as arrays of characters processed sequentially.

What is the time complexity of Camelcase Matching?

The optimal solution runs in O(q * n) time where q is the number of queries and n is the average query length. Each query is scanned once using two pointers. Space complexity is O(1) because only a few pointer variables are used.

Description Hints 3 Solution Video 6:39

1023. Camelcase Matching

Medium65.8% acceptance2 companies

Given an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches pattern, and false otherwise.

A query word queries[i] matches pattern if you can insert lowercase English letters pattern so that it equals the query. You may insert each character at any position and you may not insert any characters.

Example 1:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation: "FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

Example 2:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: [true,false,true,false,false]
Explanation: "FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".

Example 3:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
Output: [false,true,false,false,false]
Explanation: "FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".

Constraints:

1 <= pattern.length, queries.length <= 100
1 <= queries[i].length <= 100
queries[i] and pattern consist of English letters.

Asked at 2 companies

Compass

Google

Topics

Hints open one at a time

Hint 1

Given a single pattern and word, how can we solve it?

Hint 2

One way to do it is using a DP (pos1, pos2) where pos1 is a pointer to the word and pos2 to the pattern and returns true if we can match the pattern with the given word.

Hint 3

We have two scenarios: The first one is when `word[pos1] == pattern[pos2]`, then the transition will be just DP(pos1 + 1, pos2 + 1). The second scenario is when `word[pos1]` is lowercase then we can add this character to the pattern so that the transition is just DP(pos1 + 1, pos2) The case base is `if (pos1 == n && pos2 == m) return true;` Where n and m are the sizes of the strings word and pattern respectively.

6:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
"FB"

Input

["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
"FoBa"

Input

["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
"FoBaT"

Your code is saved on this device.Solution