驼峰式匹配

难度: Medium

给你一个字符串数组 queries，和一个表示模式的字符串 pattern，请你返回一个布尔数组 answer 。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。

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

示例 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 <= pattern.length, queries.length <= 100
1 <= queries[i].length <= 100
queries[i] 和 pattern 由英文字母组成

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def is_match(query, pattern):
            i, j = 0, 0
            while i < len(query) and j < len(pattern):
                if query[i] == pattern[j]:
                    i += 1
                    j += 1
                elif query[i].islower():
                    i += 1
                else:
                    return False
            while i < len(query):
                if query[i].isupper():
                    return False
                i += 1
            return j == len(pattern)

        result = []
        for query in queries:
            result.append(is_match(query, pattern))
        return result

Explain

这个题解使用了双指针的方法。我们同时遍历查询字符串 query 和模式字符串 pattern。对于 query 中的每个字符，如果它与 pattern 中的当前字符相匹配，我们就将两个指针都向前移动一位。如果它是小写字母，我们只移动 query 的指针。如果遇到一个大写字母且它与 pattern 中的当前字符不匹配，我们就直接返回 False。当我们完成遍历 query 时，我们检查 pattern 是否也被完全匹配了。

时间复杂度: O(mn)

空间复杂度: O(1)

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def is_match(query, pattern):
            i, j = 0, 0
            while i < len(query) and j < len(pattern):
                if query[i] == pattern[j]:
                    i += 1
                    j += 1
                elif query[i].islower():
                    i += 1
                else:
                    return False
            while i < len(query):
                if query[i].isupper():
                    return False
                i += 1
            return j == len(pattern)

        result = []
        for query in queries:
            result.append(is_match(query, pattern))
        return result

Explore

在驼峰式匹配中，大写字母是模式字符串中的关键字符，表示一个新的词的开始。如果在查询字符串中的大写字母与模式字符串中的当前字符不匹配，这表明模式字符串中的这部分词与查询字符串中的对应部分不同。因此，没有必要继续检查剩余字符，因为已经确定整体匹配失败。

在处理完两个字符串的匹配后，可能还有部分字符在查询字符串 `query` 中剩余。如果这些剩余的字符中含有大写字母，则表示 `query` 中还有未被 `pattern` 包含的新词的开始，这违反了驼峰式匹配的规则，即 `pattern` 必须完全覆盖 `query` 中的所有词的开始。因此，需要确认剩余的所有字符都是小写字母，以确保匹配的有效性。

如果 `pattern` 字符串较长而 `query` 字符串较短，意味着在 `query` 字符串遍历完毕后，`pattern` 中可能还有未匹配的字符。这种情况下，由于 `pattern` 的所有字符需要在 `query` 中找到对应的匹配字符，函数应该返回 `False`。在代码中，这种逻辑已经得到正确处理，即通过检查指针 `j` 是否等于 `pattern` 的长度来确认 `pattern` 是否完全被匹配。

双指针方法在处理大多数大小写混合字符串的驼峰式匹配问题时是有效的，但仍需考虑一些边界情况：1. `query` 或 `pattern` 为空字符串的情况；2. `query` 和 `pattern` 均只包含一个字符，且这个字符为大写或小写的情况；3. `query` 中包含连续的大写字母，而 `pattern` 不是这样的情况；4. `pattern` 中的字符完全不存在于 `query` 中的情况。这些情况需要通过适当的逻辑处理以确保函数的正确性和鲁棒性。