题目描述

如果我们可以将小写字母插入模式串 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

(直接查找+检查) $O(mn)$

在每个query字符串中顺序查找pattern字符串中的字符，如果没找到，直接判为False，如果找到了，那么判断从上一个index到当前index之间是否都是小写字母，如果不是，也直接判为False。直到pattern中的大写字符全部找到并且其余字符都是小写字母，判为True。

时间复杂度分析：在长度为n的query中查找长度为m的pattern中的字符，需要$O(mn)$时间复杂度

Python3 代码

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        ans = []
        lc = "abcdefghijklmnopqrstuvwxyz"
        for q in queries:
            one_ans = True
            for p in pattern:
                index = q.find(p)
                if index == -1:
                    one_ans = False
                    break
                if not all(q[i] in lc for i in range(index)):
                    one_ans = False
                    break
                q = q[index + 1:]
            if one_ans and all(qc in lc for qc in q):
                ans.append(True)
            else:
                ans.append(False)
        return ans