Camelcase Matching - Solution & Explanation

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.