1023.Camelcase Matching Leetcode using python

In [None]:

from collections import defaultdict
from pprint import pprint

1023. Camelcase Matching

leetcode

$n$ queries, where the maximum query length is $m$

In [2]:

queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
pattern = "FoBaT"

Naive

Key Idea

• Uppercase letters fit in order with given a pattern.
• Lowercase and uppercase letters match the given pattern.

Skill

all(c in it for c in s)

Check Subsequence \(O(nm)\)

In [3]:

def camelMatch(qs, p):
    def u(s):  
        """ Uppercase letters fit in order with a given pattern. """
        return [c for c in s if c.isupper()]

    def issup(s, t):
        """ Lowercase and uppercase letters match the given pattern. """
        it = iter(t)
        # return all(c in it for c in s)
        checks = []
        for c in s:
            ck = (c in it, c)
            # print(ck)
            checks.append(ck[0])
        # print(checks)
        return all(checks)
            
    return [u(p) == u(q) and issup(p, q) for q in qs]

In [4]:

q = ["FrameBuffer"]
p = "FoBa"
camelMatch(q, p)

[False]

Trie

Key Idea

• Build a trie data structure with given a pattern.
• Check every query to determine True of False.

checking process.

check every character of a query(by following the trie that was built before), where the character for each iteration is c

• c is uppercase, but has no child -> False
• c in current node’s children(c can be uppercase or lowercase) -> see next node in Trie.
• c is lowercase, but has no child -> ignore it and continue(it is not necessarily to implement.)
• When terminate checking process, return True if current node’s has isEnd flag else False

Time complexity analysis

\(O(nm)\)

In [5]:

class Solution(object):
    def camelMatch(self, queries, pattern):
        """
        :type queries: List[str]
        :type pattern: str
        :rtype: List[bool]
        """
        _root = lambda: defaultdict(_root)
        root = _root()
        cur = root
        isEnd = True
        for c in pattern:
            cur = cur[c]
        cur[isEnd] = pattern
        pprint(root)

        def check(word):
            cur = root
            for c in word:
                if c.isupper() and c not in cur:
                    return False
                elif c in cur:
                    cur = cur[c]
            return isEnd in cur

        return list(map(check, queries))

sol = Solution()

In [6]:

sol.camelMatch(queries, pattern)

defaultdict(<function Solution.camelMatch.<locals>.<lambda> at 0x7fb3744dcb90>,
            {'F': defaultdict(<function Solution.camelMatch.<locals>.<lambda> at 0x7fb3744dcb90>,
                              {'o': defaultdict(<function Solution.camelMatch.<locals>.<lambda> at 0x7fb3744dcb90>,
                                                {'B': defaultdict(<function Solution.camelMatch.<locals>.<lambda> at 0x7fb3744dcb90>,
                                                                  {'a': defaultdict(<function Solution.camelMatch.<locals>.<lambda> at 0x7fb3744dcb90>,
                                                                                    {'T': defaultdict(<function Solution.camelMatch.<locals>.<lambda> at 0x7fb3744dcb90>,
                                                                                                      {True: 'FoBaT'})})})})})})

[False, True, False, False, False]

Regex

How to use Regular Expression?

In [7]:

import re

given a pattern, build regular expression as follows.

In [8]:

q = ["FooBarTest"]
p = "FoBaT"
print("^[a-z]*" + "[a-z]*".join(p) + "[a-z]*$", p)
re.match("^[a-z]*" + "[a-z]*".join(p) + "[a-z]*$", q[0]) # return matched object if match else Nones

^[a-z]*F[a-z]*o[a-z]*B[a-z]*a[a-z]*T[a-z]*$ FoBaT

<re.Match object; span=(0, 10), match='FooBarTest'>

Key Idea

If q is matched with Regex, there is an re.object
Else, return None
Therefore, determine True or False by existence of re.object after matching process.

In [9]:

def camelMatch(qs, p):
    return [re.match("^[a-z]*" + "[a-z]*".join(p) + "[a-z]*$", q) != None for q in qs]

In [10]:

camelMatch(q, p)

[True]