Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1023. Camelcase Matching - Leetcode Solution

Code Implementation

class Solution:
    def camelMatch(self, queries, pattern):
        def is_match(query, pattern):
            i = 0
            for c in query:
                if i < len(pattern) and c == pattern[i]:
                    i += 1
                elif c.isupper():
                    return False
            return i == len(pattern)
        return [is_match(query, pattern) for query in queries]
      
class Solution {
public:
    bool isMatch(const string& query, const string& pattern) {
        int i = 0;
        for (char c : query) {
            if (i < pattern.size() && c == pattern[i]) {
                ++i;
            } else if (isupper(c)) {
                return false;
            }
        }
        return i == pattern.size();
    }
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> res;
        for (const string& query : queries) {
            res.push_back(isMatch(query, pattern));
        }
        return res;
    }
};
      
class Solution {
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> res = new ArrayList<>();
        for (String query : queries) {
            res.add(isMatch(query, pattern));
        }
        return res;
    }
    private boolean isMatch(String query, String pattern) {
        int i = 0;
        for (char c : query.toCharArray()) {
            if (i < pattern.length() && c == pattern.charAt(i)) {
                i++;
            } else if (Character.isUpperCase(c)) {
                return false;
            }
        }
        return i == pattern.length();
    }
}
      
var camelMatch = function(queries, pattern) {
    function isMatch(query, pattern) {
        let i = 0;
        for (let c of query) {
            if (i < pattern.length && c === pattern[i]) {
                i++;
            } else if (c >= 'A' && c <= 'Z') {
                return false;
            }
        }
        return i === pattern.length;
    }
    return queries.map(query => isMatch(query, pattern));
};

Problem Description

Given a list of strings queries and a string pattern, determine for each query whether it matches the pattern using camelcase rules. A query matches the pattern if we can insert any number of lowercase English letters at any position in the pattern to obtain the query, but we cannot insert uppercase letters or change the order of characters. Every uppercase letter in the pattern must appear in the query at the same position, and any extra uppercase letter in the query that does not appear in the pattern causes the match to fail. The function should return a list of booleans, one for each query in queries, indicating whether the query matches the pattern.

Thought Process

To solve this problem, we need to simulate how a pattern can be expanded into a query by inserting lowercase letters. The key insight is that the pattern's characters must appear in order in the query, and all uppercase letters in the query must be present in the pattern in the correct order and position. A brute-force approach would try all possible ways to insert lowercase letters, but this is inefficient. Instead, we can use a two-pointer technique: one pointer for the query and one for the pattern. We iterate through the query, matching characters with the pattern. If the current character in the query matches the current character in the pattern, we move both pointers forward. If it is a lowercase letter that does not match, we skip it (since lowercase insertions are allowed). If we encounter an uppercase letter in the query that does not match the pattern, the match fails. This approach is much more efficient and directly models the rules of camelcase matching.

Solution Approach

The solution uses the following steps:
  1. For each query in queries, check if it matches the pattern using a helper function.
  2. In the helper function, use two pointers: one for the query and one for the pattern.
  3. Iterate through each character in the query:
    • If the current character in the query matches the current character in the pattern, move both pointers forward.
    • If the character does not match and is a lowercase letter, skip it (move the query pointer forward only).
    • If the character does not match and is an uppercase letter, return false (match fails).
  4. After processing the query, check if the pattern pointer has reached the end of the pattern. If so, the match is successful.
  5. Return the results for all queries as a list of booleans.
This approach leverages the fact that only lowercase letters can be inserted, and all uppercase letters in the query must correspond to those in the pattern.

Example Walkthrough

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

  • "FooBar": F matches F, o and o are lowercase and skipped, B matches B. End of pattern. Match: True
  • "FooBarTest": F matches F, o and o are lowercase and skipped, B matches B, 'T' is uppercase but no more characters in pattern, so Match: False
  • "FootBall": F matches F, o, o, t are lowercase and skipped, B matches B, a, l, l are lowercase. End of pattern. Match: True
  • "FrameBuffer": F matches F, r, a, m, e are lowercase, B matches B, u, f, f, e, r are lowercase. End of pattern. Match: True
  • "ForceFeedBack": F matches F, o, r, c, e are lowercase, F matches B? No, so Match: False

The result would be [True, False, True, True, False].

Time and Space Complexity

  • Brute-force approach: Would try all possible insertions of lowercase letters, leading to exponential time complexity, which is not feasible.
  • Optimized approach (two-pointer): For each query, we scan each character once, and for each, possibly advance the pattern pointer. If there are Q queries and average length L, the time complexity is O(Q * L).
  • Space complexity: Only O(1) extra space per query (excluding the output list), so total space is O(Q) for the result.

Summary

The camelcase matching problem is efficiently solved using a two-pointer approach that checks for pattern correspondence in each query, skipping allowed lowercase insertions and ensuring all uppercase letters match exactly. This strategy avoids brute-force enumeration, is easy to implement, and leverages the problem's structural constraints for efficient matching.