Skip to content

Latest commit

 

History

History
114 lines (89 loc) · 4.86 KB

1023-camelcase-matching.md

File metadata and controls

114 lines (89 loc) · 4.86 KB

1023. Camelcase Matching - 驼峰式匹配

如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）

给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。

 

示例 1：

输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
输出：[true,false,true,true,false]
示例：
"FooBar" 可以这样生成："F" + "oo" + "B" + "ar"。
"FootBall" 可以这样生成："F" + "oot" + "B" + "all".
"FrameBuffer" 可以这样生成："F" + "rame" + "B" + "uffer".

示例 2：

输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
输出：[true,false,true,false,false]
解释：
"FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".
"FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".

示例 3：

输出：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
输入：[false,true,false,false,false]
解释： 
"FooBarTest" 可以这样生成："Fo" + "o" + "Ba" + "r" + "T" + "est".

 

提示：

  1. 1 <= queries.length <= 100
  2. 1 <= queries[i].length <= 100
  3. 1 <= pattern.length <= 100
  4. 所有字符串都仅由大写和小写英文字母组成。

题目标签：Trie / String

题目链接：LeetCode / LeetCode中国

题解

Language Runtime Memory
python3 40 ms 13.3 MB 
class Solution:
    # 缓存递归中间结果
    cache = None

    def sMatch(self, source, p, pattern, q):
        if __class__.cache[p][q] != -1:
            return __class__.cache[p][q]
        tp, tq = p, q
        if q >= len(pattern):
            # 结束匹配，检查是否还有大写字母未匹配
            while p < len(source):
                if source[p].isupper():
                    return False
                p += 1
            __class__.cache[tp][tq] = 1
            return True
        # 若当前要找的是大写字母
        if pattern[q].isupper():
            while p < len(source) and source[p] != pattern[q]:
                # 如果遇到不同的大写字母，则不匹配
                if source[p].isupper():
                    __class__.cache[tp][tq] = 0
                    return False
                p += 1
            # 如果找不到相应的大写字母
            if p == len(source):
                __class__.cache[tp][tq] = 0
                return False
            # 如果有相应的大写字母，继续向右匹配
            return self.sMatch(source, p + 1, pattern, q + 1)
        # 若当前要找的是小写字母
        else:
            # 找对应的小写字母候选位置
            while p < len(source) and source[p].islower():
                if source[p] == pattern[q]:
                    # 针对每个候选位置继续向右匹配
                    if self.sMatch(source, p + 1, pattern, q + 1):
                        __class__.cache[tp][tq] = 1
                        return True
                p += 1
            __class__.cache[tp][tq] = 0
            return False

    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        res = []
        for source in queries:
            __class__.cache = [[-1] * (len(pattern) + 1)] * (len(source) + 1)
            res.append(self.sMatch(source, 0, pattern, 0))
        return res