Camelcase Matching Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Google JP Morgan
StringViews 103

Problem Statement:

Camelcase Matching Leetcode Solution says that – Given an array of string “queries” and string “pattern”, return boolean array result where result[i] is true where “queries[i]” matches with “pattern”, false otherwise.

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

Examples:

Example 1:

Input: 
queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: 
[true,false,true,true,false]

Explanation:

Camelcase Matching Leetcode Solution

 

Example 2:

Input: 
queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: 
[true,false,true,false,false]

Approach:

Idea:

For each string in queries, we compare it with the pattern and if both match we push “true” in the result array otherwise we push “false” in the result.

  1. First, we iterate through the given queries, and for each string in the queries, we check if it matches the pattern or not.
  2. For checking, we start with index=0 which represents the character to match in the pattern.
  3. Now loop all characters in the string to be matched with the pattern.
  4. Whenever we encounter a character that is equal to pattern[index], increase index=index+1.
  5. If the character encountered is uppercase and it doesn’t match the pattern[index] returns false.
  6. Return true after all characters in the string are traversed and only if the index value is equal to the length of the Pattern.

Code:

C++ code:

class Solution {
public:
    bool isCheck(string query, string pattern){
        int i=0;
        for(auto c:query){
            if(i<pattern.size() && c==pattern[i]) i++;
            else if(c>='A' && c<='Z') return false;
        }
        if(i==pattern.size()) return true;
        return false;
    }
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> result;
        for(auto i:queries){
            if(isCheck(i, pattern)){
                result.push_back(true);
            }
            else{
                result.push_back(false);
            }
        }
        return result;
    }
};

Java code:

class Solution {
    public Boolean isCheck(String query, String pattern){
        int i=0;
        for(int c=0;c<query.length();c++){
            if(i<pattern.length() && query.charAt(c)==pattern.charAt(i)) i++;
            else if(query.charAt(c) >= 'A' && query.charAt(c) <= 'Z') return false;
        }
        if(i==pattern.length()) return true;
        return false;
    }
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> result = new ArrayList<>();
        for(int i=0;i<queries.length;i++){
            if(isCheck(queries[i], pattern)){
                result.add(true);
            }
            else{
                result.add(false);
            }
        }
        return result;
    }
}

Complexity Analysis for Camelcase Matching Leetcode Solution:

Time Complexity:

The time complexity will be O(N*M) where N = the length of the “queries” and M= the length of the “pattern”.

Space Complexity:

The space complexity will be O(1) since no extra space is required.

Similar type of question for reference and practice:

String matching in array

 

Translate »