# 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

| Item | Meaning |
|---|---|
| Input | Array `queries` and string `pattern` |
| Output | Boolean array: `true` if the query matches the pattern |
| Match | Pattern is a subsequence of query; all uppercase in query must appear in pattern |

Function shape:

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

## Examples

Example 1:

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

| Query | Matches? | Reason |
|---|---|---|
| `"FooBar"` | Yes | `F` matches, `B` matches, no extra uppercase |
| `"FooBarTest"` | No | Extra uppercase `T` |
| `"FootBall"` | Yes | `F` matches, `B` matches |
| `"FrameBuffer"` | Yes | `F` matches, `B` matches |
| `"ForceFeedBack"` | No | Extra uppercase `F` and `B` beyond pattern |

Answer:

```python
[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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(Q * L)` | Check each character of each query once |
| Space | `O(1)` | Constant extra space per 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

```python
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:

```python
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:

```python
return j == len(pattern)
```

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---|---|
| Pattern `"FB"` | `[T,F,T,T,F]` | Only queries with exactly F and B uppercase |
| Pattern `"FoBa"` | `[T,F,T,F,F]` | More specific pattern |
| `["aa"]`, `"a"` | `[T]` | Single lowercase char can be inserted |