Course4all
Join us on telegram
Home/dsa/Trie/Camelcase Matching

Camelcase Matching

Master this topic with zero to advance depth.

Camelcase Matching

A query word matches a given pattern if we can insert lowercase letters to the pattern so that it equals the query. Return a list of booleans.

Visual Representation

Queries: ["FooBar", "FooBarTest", "FootBall"] Pattern: "FB" "FooBar" -> F-oo-B-ar -> Matches! "FooBarTest" -> F-oo-B-ar-T-est -> Extra 'T' (Uppercase) -> Fails!
Medium

Examples

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

Level I: Two Pointers (Standard Search)

Intuition

For each word, use two pointers to check if the pattern is a subsequence. Additionally, ensure that any uppercase letters in the word that are NOT in the pattern cause a mismatch.

⏱ O(N * L) where N is words, L is word length.💾 O(1)
java
class Solution {
    public List<Boolean> camelMatch(String[] words, String pattern) {
        List<Boolean> res = new ArrayList<>();
        for (String w : words) res.add(check(w, pattern));
        return res;
    }
    private boolean check(String w, String p) {
        int i = 0;
        for (char c : w.toCharArray()) {
            if (i < p.length() && c == p.charAt(i)) i++;
            else if (Character.isUpperCase(c)) return false;
        }
        return i == p.length();
    }
}
Approach 2

Level III: Two Pointers / Trie

Intuition

For each query, use two pointers (ii for query, jj for pattern). If query[i]==pattern[j]query[i] == pattern[j], increment both. If query[i]query[i] is lowercase, increment only ii. If query[i]query[i] is uppercase and doesn't match pattern[j]pattern[j], it's a mismatch. After the loop, if jj reached pattern length and no extra uppercase letters remain in query, it's a match.

⏱ O(N * L).💾 O(1) extra space.
java
import java.util.*;
class Solution {
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> res = new ArrayList<>();
        for (String q : queries) res.add(match(q, pattern));
        return res;
    }
    private boolean match(String q, String p) {
        int j = 0;
        for (char c : q.toCharArray()) {
            if (j < p.length() && c == p.charAt(j)) j++;
            else if (Character.isUpperCase(c)) return false;
        }
        return j == p.length();
    }
}
← Previous QuestionMaximum XOR of Two Numbers in an Array
Next Question →Prefix and Suffix Search