LeetCode 1023: Camelcase Matching

Problem Restatement

We are given an array of strings queries and a string pattern.

A query string matches the pattern if we can insert lowercase letters into the pattern to make it equal to the query.

In other words, the pattern is a subsequence of the query, and all uppercase letters in the query must match uppercase letters in the pattern.

Return a boolean array where result[i] is true if queries[i] matches the pattern.

The official constraints state that 1 <= pattern.length <= queries[i].length <= 100.

Input and Output

Function shape:

def camelMatch(queries: list[str], pattern: str) -> list[bool]:
    ...

Examples

Example 1:

queries = ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"]
pattern = "FB"

Answer:

[True, False, True, True, False]

Key Insight

For a query to match the pattern:

1. Every character of the pattern must appear in the query in order.
2. Every uppercase character in the query must be matched to a character in the pattern.

Use two pointers: one on the query and one on the pattern.

• If the query character equals the current pattern character, advance both pointers.
• If the query character is lowercase and doesn’t match pattern, advance only the query pointer.
• If the query character is uppercase and doesn’t match pattern, the query fails immediately.

The query matches if the pattern pointer reaches the end of the pattern.

Algorithm

Define matches(query, pattern):

1. j = 0 (pattern pointer).
2. For each character c in query:
   • If j < len(pattern) and c == pattern[j], advance j.
   • Else if c.isupper(), return False.
3. Return j == len(pattern).

Apply this to each query.

Correctness

Advancing j when characters match ensures the pattern is consumed as a subsequence.

Returning False when an uppercase character in the query doesn’t match the pattern ensures all uppercase characters in the query are accounted for by the pattern.

After processing the query, checking j == len(pattern) ensures all pattern characters were matched.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Let Q = len(queries) and L be the average length of a query.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def camelMatch(self, queries: list[str], pattern: str) -> list[bool]:
        def matches(query: str) -> bool:
            j = 0
            for c in query:
                if j < len(pattern) and c == pattern[j]:
                    j += 1
                elif c.isupper():
                    return False
            return j == len(pattern)

        return [matches(q) for q in queries]

Code Explanation

Two-pointer matching:

for c in query:
    if j < len(pattern) and c == pattern[j]:
        j += 1
    elif c.isupper():
        return False

If a query character matches the current pattern character, advance the pattern pointer.

If the query character is uppercase but doesn’t match the pattern, the query fails.

Lowercase characters that don’t match the pattern are allowed (they are the inserted letters).

After the loop, confirm the entire pattern was consumed:

return j == len(pattern)

Testing

def run_tests():
    s = Solution()

    assert s.camelMatch(
        ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"],
        "FB"
    ) == [True, False, True, True, False]

    assert s.camelMatch(
        ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"],
        "FoBa"
    ) == [True, False, True, False, False]

    assert s.camelMatch(["aa"], "a") == [True]

    print("all tests passed")

run_tests()