Domain 2MediumMEDIUM

Camelcase Matching

LeetCode problem 1023: Camelcase Matching (medium).

Domain: medium•Updated: 2026-09-06
#String#Trie

Problem Breakdown

We need to determine which strings in a list of queries can be formed by inserting zero or more lowercase letters into a given pattern string.

  • Inputs: A list of query strings (queries) and one pattern string (pattern).
  • Outputs: A boolean array where each element indicates if the corresponding query matches the pattern.
  • Matching Rule: The characters in pattern must appear as a subsequence within the query. Crucially, any character in the query that does not correspond to a character in pattern must be lowercase. If an uppercase letter appears in the query at a position where it doesn’t match the current required pattern character (or if we are past all pattern characters), the query fails.
  • Constraints: Strings contain only English letters. Lengths up to 100.

Intuition

A brute-force approach would try inserting every possible lowercase letter into pattern and checking for equality with each query. This is exponential (O(2N)O(2^N)) because we have many insertion points, making it infeasible even for small strings (lengths up to 100).

The key insight is that this problem can be modeled as a subsequence matching problem. We iterate through the query string and try to match characters against the pattern pointer:

  1. If we find an exact character match, consume both pointers.
  2. If it’s not a match but the current query character is lowercase, treat it as an “inserted” filler (skip).
  3. If it’s not a match and the query character is uppercase, this violates the rule that only lowercase letters can be inserted into pattern. Return False immediately.

Approach

We will use two pointers: one for the current position in the query (i) and one for the pattern (j). For each query string:

  1. Initialize both pointers to 0.
  2. Iterate through every character of the query using pointer i.
  3. If the characters match (q[i] == pattern[j]), advance both pointers (we found a required part).
  4. Else, check if the current query character is lowercase:
    • Yes: It’s an inserted filler we can ignore for now; increment only i.
    • No: We encountered an uppercase letter that doesn’t match the pattern requirement or exists after the pattern was fully matched. This makes it invalid; return False immediately.
  5. After iterating through all query characters, verify if we successfully consumed every character of the pattern (check if j == len(pattern)). If yes, append True to results; otherwise False.

Complexity Analysis

  • Time: O(N⋅M)O(N \cdot M) where NN is the number of queries and MM is the average length of a query string. We iterate through each character in every query exactly once. Given constraints (10410^4 total characters roughly), this is efficient enough for FAANG standards.
  • Space: O(1)O(1) auxiliary space (excluding output list).

Solution

from typing import List

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        res = []
        
        for q in queries:
            i = 0 # Pointer for query string
            j = 0 # Pointer for pattern string
            
            while i < len(q):
                if j < len(pattern) and q[i] == pattern[j]:
                    # Exact match found, consume both pointers
                    i += 1
                    j += 1
                elif not q[i].islower(): 
                    # Uppercase mismatch or extra uppercase after matching all patterns -> Invalid
                    break
                
                else:
                    # Lowercase filler character in query that doesn't match pattern char yet
                    i += 1
            
            if i == len(q) and j == len(pattern):
                res.append(True)
            else:
                res.append(False)

        return res

Edge Cases Handled

  • Pattern fully matched early: If the query contains extra characters after matching all pattern chars, they must be lowercase. The elif not q[i].islower() check catches any remaining uppercase letters and breaks/returns False.
  • Uppercase mismatch in middle: If an uppercase letter appears that doesn’t match the current required pattern char (e.g., Query “FooBar”, Pattern “FB” -> ‘o’ matches, but then query has ‘T’), it triggers not q[i].islower() and fails.
  • Pattern longer than query: The loop finishes with j < len(pattern), so the final check returns False correctly.
  • Empty extra characters at end of Query: Handled by checking if we consumed all pattern chars (j == len(pattern)).