LeetCode 1023 - Camelcase Matching

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, String, Trie, String Matching

Solution

Problem Understanding

The problem gives us a list of query strings and a target camel case pattern. For each query, we must determine whether the query can be formed by inserting only lowercase English letters into the pattern.

The important restriction is that we are only allowed to insert lowercase letters. We are not allowed to insert uppercase letters, remove characters, reorder characters, or change letter casing.

This means the uppercase structure of the query must align exactly with the uppercase structure implied by the pattern.

For example, if the pattern is "FB":

"FooBar" matches because we can insert lowercase letters:
"F" + "oo" + "B" + "ar"
"FootBall" also matches:
"F" + "oot" + "B" + "all"
"FooBarTest" does not match because the extra uppercase 'T' cannot be inserted. We are only allowed to insert lowercase letters.

The input consists of:

queries, an array of strings
pattern, the target camel case pattern

The output is a boolean array where each element indicates whether the corresponding query matches the pattern.

The constraints are relatively small:

Up to 100 queries
Each string length up to 100

This means even an O(n * m) solution, where m is the query length, is completely acceptable.

Several edge cases are important:

Queries with extra uppercase letters should fail immediately.
Queries shorter than the pattern cannot match.
Queries may contain many extra lowercase letters, which are allowed.
The pattern itself may contain lowercase letters, so matching is not purely about uppercase characters.
Exact matches should also return true.

Approaches

Brute Force Approach

A brute force idea is to explicitly attempt all possible ways of inserting lowercase letters into the pattern and check whether the resulting string equals the query.

Conceptually, for every query:

Start with the pattern.
Try inserting lowercase letters at every possible position.
Generate all possible candidate strings.
Check whether any generated string equals the query.

This works because the definition of matching is literally based on inserting lowercase letters into the pattern.

However, this approach is computationally infeasible because the number of insertion combinations grows exponentially with the query length. Even for moderate string sizes, the number of generated candidates becomes enormous.

Although the constraints are small, exponential generation is still unnecessary and inefficient.

Optimal Two Pointer Approach

The key observation is that we never actually need to generate strings.

Instead, we only need to verify whether the query can be traversed while consuming the pattern characters in order.

The rules are:

If the current query character matches the current pattern character, advance both pointers.
If the query character is lowercase and does not match, we may skip it because lowercase insertions are allowed.
If the query character is uppercase and does not match, the query is invalid immediately because uppercase letters cannot be inserted arbitrarily.

At the end:

All pattern characters must be matched.
Any remaining query characters must all be lowercase.

This naturally leads to a linear two pointer scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Generates all possible lowercase insertions
Optimal	O(Q × L)	O(1)	Two pointer scan for each query

Here:

Q = number of queries
L = maximum query length

Algorithm Walkthrough

Optimal Two Pointer Algorithm

Iterate through every query in queries.

We process each query independently because the matching condition depends only on the current query and the shared pattern. 2. Initialize two pointers.

Use:

i for the query
j for the pattern

Both start at 0. 3. Traverse the query from left to right.

At each step, compare query[i] with pattern[j]. 4. If the characters match, advance both pointers.

This means the current pattern character has been successfully matched in order. 5. If the characters do not match, check whether query[i] is lowercase.

If it is lowercase, skip it by advancing only i.

This corresponds to inserting an extra lowercase character into the pattern. 6. If the characters do not match and query[i] is uppercase, return false.

Uppercase letters cannot appear unless they are explicitly matched by the pattern. 7. Continue until the entire query has been processed. 8. After traversal, verify that the entire pattern was matched.

This means j == len(pattern).

If not, some required pattern characters were never found. 9. Store the result for the current query. 10. Return the final boolean array.

Why it works

The algorithm maintains the invariant that all characters before pointer j in the pattern have already been matched in order within the query.

Lowercase query characters may always be skipped because the problem allows inserting lowercase letters anywhere into the pattern.

Uppercase query characters cannot be skipped because uppercase insertions are not allowed. Therefore, every uppercase letter in the query must correspond exactly to a pattern character.

Because the algorithm checks all characters in order while enforcing these rules, it correctly determines whether the query can be formed from the pattern.

Python Solution

from typing import List

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def matches(query: str, pattern: str) -> bool:
            pattern_index = 0
            pattern_length = len(pattern)

            for char in query:
                if pattern_index < pattern_length and char == pattern[pattern_index]:
                    pattern_index += 1
                elif char.isupper():
                    return False

            return pattern_index == pattern_length

        return [matches(query, pattern) for query in queries]

The implementation defines a helper function called matches that checks whether a single query matches the pattern.

The variable pattern_index tracks how many characters from the pattern have already been matched.

The loop iterates through every character in the query:

If the current query character matches the next required pattern character, we advance pattern_index.
Otherwise, if the query character is uppercase, the query becomes invalid immediately.
Lowercase mismatches are ignored because lowercase insertions are allowed.

After processing the entire query, the function verifies that all pattern characters were consumed. If not, the query failed to match completely.

Finally, the main function applies this helper to every query and returns the resulting boolean list.

Go Solution

func camelMatch(queries []string, pattern string) []bool {
	result := make([]bool, len(queries))

	for i, query := range queries {
		result[i] = matches(query, pattern)
	}

	return result
}

func matches(query string, pattern string) bool {
	patternIndex := 0
	patternLength := len(pattern)

	for _, char := range query {
		if patternIndex < patternLength && byte(char) == pattern[patternIndex] {
			patternIndex++
		} else if char >= 'A' && char <= 'Z' {
			return false
		}
	}

	return patternIndex == patternLength
}

The Go implementation follows the same logic as the Python version.

One small difference is uppercase detection. Instead of using a built in helper like isupper(), the code checks whether the rune lies between 'A' and 'Z'.

The solution uses a helper function to keep the logic modular and readable.

Since the constraints are small and only English letters are involved, using byte indexing for the pattern is completely safe.

Worked Examples

Example 1

Input:

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

Query: `"FooBar"`

Step	Query Char	Pattern Char	Action	Pattern Index
1	F	F	Match both	1
2	o	B	Skip lowercase	1
3	o	B	Skip lowercase	1
4	B	B	Match both	2
5	a	done	Skip lowercase	2
6	r	done	Skip lowercase	2

Final result: true

Query: `"FooBarTest"`

Step	Query Char	Pattern Char	Action
1	F	F	Match
2	o	B	Skip
3	o	B	Skip
4	B	B	Match
5	a	done	Skip
6	r	done	Skip
7	T	done	Uppercase mismatch, fail

Final result: false

Query: `"FootBall"`

Step	Query Char	Pattern Char	Action
1	F	F	Match
2	o	B	Skip
3	o	B	Skip
4	t	B	Skip
5	B	B	Match
6	a	done	Skip
7	l	done	Skip
8	l	done	Skip

Final result: true

Query: `"FrameBuffer"`

Step	Query Char	Pattern Char	Action
1	F	F	Match
2	r	B	Skip
3	a	B	Skip
4	m	B	Skip
5	e	B	Skip
6	B	B	Match
7	u	done	Skip
8	f	done	Skip
9	f	done	Skip
10	e	done	Skip
11	r	done	Skip

Final result: true

Query: `"ForceFeedBack"`

Step	Query Char	Pattern Char	Action
1	F	F	Match
2	o	B	Skip
3	r	B	Skip
4	c	B	Skip
5	e	B	Skip
6	F	B	Uppercase mismatch, fail

Final result: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(Q × L)	Each query is scanned once
Space	O(1)	Only pointer variables are used

The algorithm processes every character of every query exactly once.

No additional data structures proportional to the input size are created, so the auxiliary space usage remains constant.

Test Cases

from typing import List

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def matches(query: str, pattern: str) -> bool:
            pattern_index = 0

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

            return pattern_index == len(pattern)

        return [matches(query, pattern) for query in queries]

solution = Solution()

# Example 1
assert solution.camelMatch(
    ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"],
    "FB"
) == [True, False, True, True, False]

# Example 2
assert solution.camelMatch(
    ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"],
    "FoBa"
) == [True, False, True, False, False]

# Example 3
assert solution.camelMatch(
    ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"],
    "FoBaT"
) == [False, True, False, False, False]

# Exact match
assert solution.camelMatch(
    ["FooBar"],
    "FooBar"
) == [True]

# Extra lowercase letters allowed
assert solution.camelMatch(
    ["FooooBaaaar"],
    "FB"
) == [True]

# Extra uppercase letter should fail
assert solution.camelMatch(
    ["FooBarZ"],
    "FB"
) == [False]

# Query shorter than pattern
assert solution.camelMatch(
    ["FB"],
    "FooBar"
) == [False]

# Lowercase only insertions
assert solution.camelMatch(
    ["FoBa"],
    "FB"
) == [True]

# Missing uppercase match
assert solution.camelMatch(
    ["Foo"],
    "FB"
) == [False]

# Multiple queries mixed
assert solution.camelMatch(
    ["ABC", "ABc", "AbC", "abc"],
    "ABC"
) == [True, True, False, False]

Test	Why
Example 1	Validates basic camel case matching
Example 2	Tests mixed uppercase and lowercase pattern
Example 3	Tests longer pattern with additional uppercase requirement
Exact match	Ensures identical strings match
Extra lowercase letters allowed	Confirms lowercase insertions are permitted
Extra uppercase letter should fail	Verifies uppercase mismatches invalidate queries
Query shorter than pattern	Ensures incomplete matches fail
Lowercase only insertions	Confirms lowercase skips work correctly
Missing uppercase match	Tests incomplete uppercase alignment
Multiple queries mixed	Validates behavior across diverse cases

Edge Cases

One important edge case occurs when the query contains extra uppercase letters after the pattern has already been fully matched. For example, "FooBarTest" with pattern "FB" should fail because the trailing uppercase 'T' cannot be inserted. A naive implementation might stop once the pattern is matched and incorrectly return true. This implementation continues scanning the remaining query characters and rejects any unmatched uppercase letters.

Another important edge case is when the query is shorter than the pattern. For example, query "FB" and pattern "FooBar" cannot match because some pattern characters are never found. The implementation handles this by verifying at the end that every pattern character has been consumed.

A third important edge case involves lowercase mismatches. For example, "FooooBaaaar" should match "FB" even though many extra lowercase letters appear between matching characters. A buggy implementation might require contiguous matching. This solution correctly skips lowercase characters whenever they do not match the current pattern character.

A fourth edge case appears when uppercase letters align incorrectly. For example, "ForceFeedBack" does not match "FB" because the second uppercase letter is 'F' instead of 'B'. The implementation immediately rejects uppercase mismatches, guaranteeing correctness for camel case structure validation.

LeetCode 1023 - Camelcase Matching

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Two Pointer Approach

Algorithm Walkthrough

Optimal Two Pointer Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Query: "FooBar"

Query: "FooBarTest"

Query: "FootBall"

Query: "FrameBuffer"

Query: "ForceFeedBack"

Complexity Analysis

Test Cases

Edge Cases

Query: `"FooBar"`

Query: `"FooBarTest"`

Query: `"FootBall"`

Query: `"FrameBuffer"`

Query: `"ForceFeedBack"`