Camelcase Matching - Leetcode Solution

Problem statement:

Given an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches the pattern, and false otherwise.

A query word queries[i] matches pattern if you can insert lowercase English letters pattern so that it equals the query. You may insert each character at any position and you may not insert any characters.

Example:

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" + "ootB" + "all". "FrameBuffer" can be generated like this "F" + "rames" + "B" + "uffer".

Solution:

To solve this problem, we can iterate over all the strings in queries and for each string, we can check if they match the pattern by iterating over the characters of the string and the pattern one by one.

If the current character in the pattern is equal to the current character in the string, we can move both pointers ahead. Otherwise, we need to check if the current character in the string is uppercase. If it is, we can immediately return false as we cannot insert any lowercase characters before it.

If the character in the pattern is not equal to the character in the string but the character in the string is lowercase, we can simply move ahead in the string as we can always insert the current character in the pattern before it.

At the end of the iteration, if we have reached the end of both the string and the pattern, we can return true as we have successfully matched the pattern. Otherwise, we need to return false as the pattern could not be matched.

Code:

class Solution { public: vector<bool> camelMatch(vector<string>& queries, string pattern) { vector<bool> answer; for(auto query : queries) { answer.emplace_back(match(query, pattern)); } return answer; }

bool match(string query, string pattern) {
    int i = 0, j = 0;
    while(i < query.size() && j < pattern.size()) {
        if(query[i] == pattern[j]) {
            i++, j++;
        } else if(isupper(query[i])) {
            return false;
        } else {
            i++;
        }
    }
    while(i < query.size()) {
        if(isupper(query[i])) {
            return false;
        }
        i++;
    }
    return j == pattern.size();
}

};

1