Skip to main content
Talentd

Camelcase Matching - Solution & Explanation

MediumArrayTwo PointersStringTrie15 min readAsked at: Google, Compass
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive a list of query strings and a camelCase pattern. A query matches the pattern if you can insert lowercase letters into the pattern to form the query without changing the order of the pattern’s characters. Any extra uppercase letter that does not appear in the pattern immediately invalidates the match.

The challenge is verifying that uppercase characters align exactly with the pattern while allowing extra lowercase characters anywhere. Each query must be checked independently, which makes careful character comparison the key part of the algorithm.

Approach 1: Two-Pointer Technique (O(q * n) time, O(1) space)

This approach scans each query and the pattern using two pointers. One pointer walks through the query while the other tracks the current position in the pattern. When characters match, both pointers advance. If the query character is lowercase and doesn't match, it can be skipped. If it is uppercase and doesn't match the pattern, the query immediately fails because uppercase letters cannot be inserted arbitrarily.

The key insight: uppercase letters must match exactly and in order, while lowercase letters act as "fillers" that can be ignored. You iterate through the query once, making the check linear for each query. This solution uses only constant extra memory and is typically the expected interview solution when working with two pointers and string processing.

Approach 2: Regular Expression Matching (O(q * n) time, O(n) space)

The pattern can be converted into a regular expression that enforces the camelCase constraints. For example, between every pattern character you allow any number of lowercase letters using [a-z]*. The regex becomes something like ^[a-z]*P[a-z]*a[a-z]*t[a-z]*... depending on the pattern characters. Each query is then tested against this compiled expression.

This approach is concise in languages with strong regex support such as Python or JavaScript. However, it introduces regex engine overhead and requires building the pattern dynamically. While the complexity remains linear relative to query length, the constant factors are higher than the manual scan.

Recommended for interviews: The Two-Pointer Technique is the expected solution. It demonstrates control over string traversal, conditional checks for uppercase characters, and constant-space design. Regex can be a quick implementation in production code, but interviewers generally prefer the explicit pointer-based logic because it clearly shows how you enforce the camelCase rules. The problem mainly tests string processing skills and pattern validation using ideas common in array traversal and pointer scanning.

Approach 1: Two-Pointer Technique

This approach uses a two-pointer technique to check if each query can match the pattern.

Traverse over both the query and pattern with a pointer for each. If the characters match, move both pointers; if not, just move the pointer of the query. The key is to ensure all uppercase letters in the query are matched by the pattern in order.

We define a helper function matches that checks whether a single query matches the pattern using two pointers. The main function camelMatch iterates over all the queries and uses matches to generate the result boolean array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of queries and m is the average length of the queries.

Space Complexity: O(n), for storing the results.

Try this approach in the editor →

Approach 2: Regular Expression Matching

This approach involves creating regular expressions from the patterns and matching them against each query directly.

Construct a regex pattern by translating the given pattern where each uppercase letter is preceded by a regex for any lowercase letters. We then apply this regex to each query.

In JavaScript, convert the pattern into a regex pattern by appending [a-z]* after each character, then match it against each query using the test method.

Code

JavaScriptPython

JavaScript

Python

Complexity

Time Complexity: Depends on regex engine but generally O(n * m), where n is the number of queries and m is the average length of the queries.

Space Complexity: O(n), for storing results.

Try this approach in the editor →

Approach 3: Two Pointers

We can traverse every string in queries and check whether it matches pattern or not. If it matches, we add true to the answer array, otherwise we add false.

Next, we implement a function check(s, t) to check whether the string s matches the string t.

We can use two pointers i and j to traverse the two strings. If the characters pointed to by i and j are not the same and s[i] is a lowercase letter, then we move the pointer i to the next position.

If the pointer i has reached the end of the string s or the characters pointed to by i and j are not the same, we return false. Otherwise, we move both pointers i and j to the next position. When the pointer j reaches the end of the string t, we need to check if the remaining characters in the string s are all lowercase letters. If so, we return true, otherwise we return false.

Time complexity (n times m), where n and m are the length of the array queries and the string pattern respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Technique

Time Complexity: O(n * m), where n is the number of queries and m is the average length of the queries.

Space Complexity: O(n), for storing the results.

Regular Expression Matching

Time Complexity: Depends on regex engine but generally O(n * m), where n is the number of queries and m is the average length of the queries.

Space Complexity: O(n), for storing results.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(q * n)O(1)Best general solution; efficient for iterating through each query and validating uppercase alignment
Regular Expression MatchingO(q * n)O(n)Useful when regex libraries are available and quick pattern construction is preferred

Video Solution

1023. Camelcase Matching | LEETCODE MEDIUM | STRING MATCHING • code Explainer • 2,187 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Camelcase Matching with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays