Problem statement

https://leetcode.com/problems/camelcase-matching/

Solution

What we need to check for each pair (q, pattern) is:

  1. If q is subsequence of pattern, reuse classical problem Leetcode 0392. Is Subsequence.
  2. If number of capital letters in q and pattern is the same.

Complexity

It is O(n) for time and space, where n is the total length of all queries.

Code

class Solution:
    def camelMatch(self, queries, pattern):
        def isSubsequence(s, t):
            t = iter(t)
            return all(c in t for c in s)
        
        ans, up_cnt = [], sum(i.isupper() for i in pattern)
        for q in queries:
            if not isSubsequence(pattern, q) or sum(i.isupper() for i in q) != up_cnt:
                ans += [False]
            else:
                ans += [True]
                
        return ans