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
patternmust appear as a subsequence within thequery. Crucially, any character in thequerythat does not correspond to a character inpatternmust be lowercase. If an uppercase letter appears in thequeryat 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 () 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:
- If we find an exact character match, consume both pointers.
- If it’s not a match but the current query character is lowercase, treat it as an “inserted” filler (skip).
- 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:
- Initialize both pointers to 0.
- Iterate through every character of the query using pointer
i. - If the characters match (
q[i] == pattern[j]), advance both pointers (we found a required part). - 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.
- Yes: It’s an inserted filler we can ignore for now; increment only
- After iterating through all query characters, verify if we successfully consumed every character of the
pattern(check ifj == len(pattern)). If yes, append True to results; otherwise False.
Complexity Analysis
- Time: where is the number of queries and is the average length of a query string. We iterate through each character in every query exactly once. Given constraints ( total characters roughly), this is efficient enough for FAANG standards.
- Space: 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)).