Camelcase Matching
MedPrompt
Given an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches pattern, and false otherwise.
A query word queries[i] matches pattern if you can insert lowercase English letters into the pattern so that it equals the query. You may insert a character at any position in pattern or you may choose not to insert any characters at all.
Example 1:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation: "FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".Example 2:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: [true,false,true,false,false]
Explanation: "FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".Example 3:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
Output: [false,true,false,false,false]
Explanation: "FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".
Constraints:
1 <= pattern.length, queries.length <= 1001 <= queries[i].length <= 100queries[i]andpatternconsist of English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion to solve the problem by breaking it down into smaller subproblems. We define a helper function that checks if a suffix of the query matches a suffix of the pattern. The state of our recursion is determined by the current indices in the query and pattern strings.
Algorithm
- For each query, call a recursive helper function, for instance
match(query, pattern, q_idx, p_idx), initialized withq_idx = 0andp_idx = 0. - The recursive function
matchwill have the following logic:- Base Case 1: If the pattern pointer
p_idxhas reached the end of thepattern, it means we have successfully matched all characters of the pattern. The remaining part of thequery(fromq_idxonwards) must only contain lowercase letters. If it does, we have a match; otherwise, we don't. - Base Case 2: If the query pointer
q_idxhas reached the end of thequerybut the pattern pointerp_idxhas not, it means we couldn't find matches for all pattern characters. This is a mismatch. - Recursive Step 1: If
query.charAt(q_idx)is the same aspattern.charAt(p_idx), it's a direct match. We advance both pointers and make a recursive call:match(query, pattern, q_idx + 1, p_idx + 1). - Recursive Step 2: If the characters do not match, we check if
query.charAt(q_idx)is an uppercase letter. If it is, it's an invalid character that cannot be inserted, so we have a mismatch. - Recursive Step 3: If the characters do not match and
query.charAt(q_idx)is a lowercase letter, we can treat it as an inserted character. We skip this character in the query and try to match the same pattern character with the next character in the query. We make a recursive call:match(query, pattern, q_idx + 1, p_idx).
- Base Case 1: If the pattern pointer
Walkthrough
The core of this method is a recursive function, say isMatch(q_idx, p_idx), which returns true if the substring query[q_idx...] can be matched by pattern[p_idx...].
In each call, we compare the characters at the current pointers. If they match, we advance both pointers and recurse. If they don't match, we can only proceed if the character in the query is lowercase (representing an insertion); in this case, we advance only the query pointer and recurse. If the query character is uppercase and doesn't match, it's an invalid sequence. The recursion terminates when we exhaust either the query or the pattern, with specific checks to validate the match.
class Solution { public List<Boolean> camelMatch(String[] queries, String pattern) { List<Boolean> result = new ArrayList<>(); for (String query : queries) { result.add(isMatch(query, pattern, 0, 0)); } return result; } private boolean isMatch(String query, String pattern, int qIdx, int pIdx) { // Base case: Pattern is fully matched. // Check if remaining query characters are all lowercase. if (pIdx == pattern.length()) { for (int i = qIdx; i < query.length(); i++) { if (Character.isUpperCase(query.charAt(i))) { return false; } } return true; } // Base case: Query is exhausted but pattern is not. if (qIdx == query.length()) { return false; } // If characters match, advance both pointers. if (query.charAt(qIdx) == pattern.charAt(pIdx)) { return isMatch(query, pattern, qIdx + 1, pIdx + 1); } // If query character is uppercase and doesn't match, it's a failure. else if (Character.isUpperCase(query.charAt(qIdx))) { return false; } // If query character is lowercase, it's an insertion. Advance query pointer only. else { return isMatch(query, pattern, qIdx + 1, pIdx); } }}Complexity
Time
O(N * M), where N is the number of queries and M is the maximum length of a query. Each recursive path explores the query string once.
Space
O(M + N), where N is the number of queries and M is the maximum length of a query. O(N) is for the output list, and O(M) is for the recursion call stack in the worst case for each query.
Trade-offs
Pros
The logic is a direct translation of the problem's recursive definition.
Can be easier to reason about for those comfortable with recursion.
Cons
Higher space complexity due to recursion stack.
Can be slower than an iterative approach due to function call overhead.
Risk of
StackOverflowErrorfor very long input strings, although not an issue with the given constraints.
This approach leverages the power of regular expressions to define the matching criteria. We can dynamically build a regex pattern from the input pattern string. This regex will then be used to validate each query string.
Algorithm
- First, construct a regular expression from the given
pattern. - The regex should allow for any number of lowercase letters to be inserted between the characters of the
pattern, as well as at the beginning and end. - A suitable regex can be built by starting with
^[a-z]*, then for each charactercin thepattern, appendingcfollowed by[a-z]*, and finally appending$at the end. - For a
patternlike"FoBa", the generated regex would be"^[a-z]*F[a-z]*o[a-z]*B[a-z]*a[a-z]*$". - The
^and$anchors ensure the entire query string must match the pattern. - The
[a-z]*component matches zero or more lowercase letters. - This regex correctly enforces that any uppercase letters in the query must be exactly those present in the pattern, in the correct order.
- Iterate through each
queryand use the standard library's regex matching function (e.g.,String.matches()in Java) to check if it matches the constructed regex.
Walkthrough
The matching rule can be translated into a regular expression. A query matches if it's composed of the pattern's characters in sequence, with optional lowercase letters interspersed. For a pattern p, we can construct a regex that looks for p_1 followed by lowercase letters, then p_2 followed by lowercase letters, and so on.
For example, if pattern is "FB", the regex is "^[a-z]*F[a-z]*B[a-z]*$". This pattern dictates that the string must start, have some lowercase letters (or none), then 'F', then some lowercase letters, then 'B', and then some lowercase letters until the end. This structure implicitly disallows any other uppercase letters from appearing in the query.
import java.util.ArrayList;import java.util.List; class Solution { public List<Boolean> camelMatch(String[] queries, String pattern) { StringBuilder regexBuilder = new StringBuilder("^[a-z]*"); for (char c : pattern.toCharArray()) { regexBuilder.append(c).append("[a-z]*"); } regexBuilder.append("$"); String regex = regexBuilder.toString(); List<Boolean> result = new ArrayList<>(); for (String query : queries) { result.add(query.matches(regex)); } return result; }}Complexity
Time
O(N * (P + M)), where N is the number of queries, P is the pattern length, and M is the query length. Building the regex takes O(P). For this specific type of regex, matching is typically linear in the query length, O(M).
Space
O(P + N), where P is the length of the pattern and N is the number of queries. O(P) space is needed to store the regex string and the compiled pattern object. O(N) is for the output list.
Trade-offs
Pros
Elegant and concise implementation, especially in languages with built-in regex support.
Offloads the complex matching logic to a highly optimized, standard library component.
Cons
Can be less performant than a direct iterative solution due to the overhead of regex compilation and the generality of the matching engine.
The logic might be less transparent compared to a manual two-pointer implementation.
Constructing the correct regex requires careful thought.
The most efficient approach uses two pointers to iterate through the query and pattern strings simultaneously in a single pass. This method avoids the overhead of recursion and the complexity of regular expressions, providing a direct and optimal solution.
Algorithm
- For each
query, we use a helper functionisMatch(query, pattern)to determine if it's a match. - Inside
isMatch, initialize two pointers:ifor thequerystring andjfor thepatternstring, both starting at0. - Iterate through the
querystring using pointeri. - In each iteration, compare
query.charAt(i)withpattern.charAt(j).- If
jis within the bounds ofpatternand the characters match (query.charAt(i) == pattern.charAt(j)), it means we've found the next character of the pattern. We then increment both pointersiandj. - If the characters do not match, we check if
query.charAt(i)is an uppercase letter. If it is, this uppercase letter is not part of the pattern, which violates the matching rule. We can immediately returnfalse. - If
query.charAt(i)is a lowercase letter, it can be considered an inserted character. We simply increment the query pointeri, leavingjunchanged, and continue checking.
- If
- After the loop finishes (i.e.,
ihas traversed the entirequery), we must check if we have matched all characters of thepattern. This is true if and only if the pattern pointerjhas reached the end of thepattern(j == pattern.length()).
Walkthrough
This method involves a linear scan through the query string while trying to match characters from the pattern string in order. We use a pointer i for the query and j for the pattern.
We advance i through the query. If query[i] matches pattern[j], we advance both i and j. If they don't match, we have two cases: if query[i] is uppercase, it's an invalid match. If query[i] is lowercase, we consider it an insertion and just advance i. After checking all characters in the query, a valid match requires that we have successfully found all characters of the pattern (i.e., j has reached the end of pattern).
class Solution { public List<Boolean> camelMatch(String[] queries, String pattern) { List<Boolean> ans = new ArrayList<>(); for (String query : queries) { ans.add(isMatch(query, pattern)); } return ans; } private boolean isMatch(String query, String pattern) { int j = 0; // pattern pointer for (int i = 0; i < query.length(); i++) { // query pointer char qChar = query.charAt(i); if (j < pattern.length() && qChar == pattern.charAt(j)) { j++; } else if (Character.isUpperCase(qChar)) { return false; } } return j == pattern.length(); }}Complexity
Time
O(N * M), where N is the number of queries and M is the maximum length of a query. Each query is processed in a single linear scan.
Space
O(N), where N is the number of queries. The space is dominated by the output list. The auxiliary space required per query is O(1).
Trade-offs
Pros
Optimal time complexity as it processes each query in a single pass.
Minimal space complexity, using only a constant amount of extra space per query.
Direct and easy-to-understand implementation without external dependencies or complex machinery.
Cons
Requires careful manual implementation of the pointer logic to handle all edge cases correctly.
Solutions
Solution
class Solution {public List<Boolean> camelMatch(String[] queries, String pattern) { List<Boolean> ans = new ArrayList<>(); for (var q : queries) { ans.add(check(q, pattern)); } return ans; }private boolean check(String s, String t) { int m = s.length(), n = t.length(); int i = 0, j = 0; for (; j < n; ++i, ++j) { while (i < m && s.charAt(i) != t.charAt(j) && Character.isLowerCase(s.charAt(i))) { ++i; } if (i == m || s.charAt(i) != t.charAt(j)) { return false; } } while (i < m && Character.isLowerCase(s.charAt(i))) { ++i; } return i == m; }}class Solution {public: vector<bool> camelMatch(vector<string> &queries, string pattern) { vector<bool> ans; auto check = [](string &s, string &t) { int m = s.size(), n = t.size(); int i = 0, j = 0; for (; j < n; ++i, ++j) { while (i < m && s[i] != t[j] && islower(s[i])) { ++i; } if (i == m || s[i] != t[j]) { return false; } } while (i < m && islower(s[i])) { ++i; } return i == m; }; for (auto &q : queries) { ans.push_back(check(q, pattern)); } return ans; }};class Solution: def camelMatch(self, queries: List[str], pattern: str) -> List[bool]: def check(s, t): m, n = len(s), len(t) i = j = 0 while j < n: while i < m and s[i] != t[j] and s[i]. islower(): i += 1 if i == m or s[i] != t[j]: return False i, j = i + 1, j + 1 while i < m and s[i]. islower(): i += 1 return i == m return [check(q, pattern) for q in queries]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.