# Camelcase Matching
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/camelcase-matching)
Canonical: https://scaleengineer.com/dsa/problems/camelcase-matching
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** Array, String, Trie
**Companies:** [Compass](https://scaleengineer.com/companies/compass)
---
## Problem
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 <= 100`
* `1 <= queries[i].length <= 100`
* `queries[i]` and `pattern` consist of English letters.

# Approaches
## Recursive Matching
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.
**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.
**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 `StackOverflowError` for very long input strings, although not an issue with the given constraints.
### Explanation
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.

```java
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);
        }
    }
}
```
### Algorithm
- For each query, call a recursive helper function, for instance `match(query, pattern, q_idx, p_idx)`, initialized with `q_idx = 0` and `p_idx = 0`.
- The recursive function `match` will have the following logic:
  - **Base Case 1:** If the pattern pointer `p_idx` has reached the end of the `pattern`, it means we have successfully matched all characters of the pattern. The remaining part of the `query` (from `q_idx` onwards) must only contain lowercase letters. If it does, we have a match; otherwise, we don't.
  - **Base Case 2:** If the query pointer `q_idx` has reached the end of the `query` but the pattern pointer `p_idx` has 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 as `pattern.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)`.

## Regular Expression Matching
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 character `c` in the `pattern`, appending `c` followed by `[a-z]*`, and finally appending `$` at the end.
- For a `pattern` like `"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 `query` and use the standard library's regex matching function (e.g., `String.matches()` in Java) to check if it matches the constructed regex.

## Two-Pointer Iteration
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.
**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).
**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.
### Explanation
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`).

```java
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();
    }
}
```
### Algorithm
- For each `query`, we use a helper function `isMatch(query, pattern)` to determine if it's a match.
- Inside `isMatch`, initialize two pointers: `i` for the `query` string and `j` for the `pattern` string, both starting at `0`.
- Iterate through the `query` string using pointer `i`.
- In each iteration, compare `query.charAt(i)` with `pattern.charAt(j)`.
  - If `j` is within the bounds of `pattern` and the characters match (`query.charAt(i) == pattern.charAt(j)`), it means we've found the next character of the pattern. We then increment both pointers `i` and `j`.
  - 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 return `false`.
  - If `query.charAt(i)` is a lowercase letter, it can be considered an inserted character. We simply increment the query pointer `i`, leaving `j` unchanged, and continue checking.
- After the loop finishes (i.e., `i` has traversed the entire `query`), we must check if we have matched all characters of the `pattern`. This is true if and only if the pattern pointer `j` has reached the end of the `pattern` (`j == pattern.length()`).

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```