What is Camelcase Matching?

Camelcase Matching is a problem where you match queries to a given pattern using a two-pointer approach, ensuring the correct case-sensitive alignment of letters.

How does the two-pointer technique work in Camelcase Matching?

The two-pointer technique uses one pointer to traverse the pattern and another to scan through each query, checking for alignment of uppercase characters and skipping lowercase ones.

What should I be cautious about while solving Camelcase Matching?

Be mindful of case sensitivity and the need to handle multiple queries efficiently. Incorrect pointer movement or case handling may lead to false negatives.

What is the time complexity of the Camelcase Matching solution?

The time complexity is O(n * m), where `n` is the number of queries and `m` is the average length of the queries. This is due to the need to check each query against the pattern.

What are the common errors in Camelcase Matching?

Common errors include misaligning uppercase characters, not properly skipping lowercase letters, and inefficient pointer management, leading to slower solutions.

#1023

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

驼峰式匹配

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

数组双指针字符串字典树字符串匹配

题目描述

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

如果可以将 小写字母 插入模式串 pattern 得到待查询项 queries[i]，那么待查询项与给定模式串匹配。您可以在模式串中的任何位置插入字符，也可以选择不插入任何字符。

示例 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 由英文字母组成

lightbulb

解题思路

方法一：双指针

我们可以遍历 queries 中的每个字符串，判断其是否与 pattern 匹配，若匹配则将 true 加入答案数组，否则加入 false。

接下来，我们实现一个 $check(s, t)$ 函数，用于判断字符串 $s$ 和 $t$ 是否匹配。

我们可以使用双指针 $i$ 和 $j$ ，分别指向两个字符串的首字符，然后遍历两个字符串。如果指针 $i$ 和 $j$ 指向的字符不同，并且 $s[i]$ 为小写字母，则指针 $i$ 循环向后移动一位。

如果指针 $i$ 已经到达字符串 $s$ 的末尾，或者指针 $i$ 和 $j$ 指向的字符不同，则返回 false。否则，指针 $i$ 和 $j$ 同时向后移动一位。当指针 $j$ 到达字符串 $t$ 的末尾时，我们需要判断字符串 $s$ 中剩余的字符是否都为小写字母，若是则返回 true，否则返回 false。

时间复杂度 $(n \times m)$ ，其中 $n$ 和 $m$ 分别为数组 queries 的长度和字符串 pattern 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def check(s, t):
            m, n = len(s), len(t)
            i = j = 0
            while j < n:
                while i < m and s[i] != t[j] and s[i].islower():
                    i += 1
                if i == m or s[i] != t[j]:
                    return False
                i, j = i + 1, j + 1
            while i < m and s[i].islower():
                i += 1
            return i == m

        return [check(q, pattern) for q in queries]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate effectively demonstrates two-pointer scanning and how it is used to match the query and pattern.
question_mark
The candidate explains invariant tracking as a core concept for ensuring that the pattern's case constraints are respected during matching.
question_mark
The candidate considers time and space efficiency when processing multiple queries, showing understanding of problem scale.

warning

常见陷阱

外企场景

error
Failing to properly match uppercase characters, causing incorrect results when letters are skipped.
error
Not accounting for the case sensitivity of the pattern, leading to false negatives when lowercase letters are inserted improperly.
error
Mismanaging the two-pointer movement, resulting in unnecessary comparisons and inefficient matching logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Matching multiple queries with different pattern lengths, requiring a dynamic approach for varying input sizes.
arrow_right_alt
Supporting more complex patterns that may contain both uppercase and lowercase letters interspersed within the pattern.
arrow_right_alt
Incorporating additional constraints, such as ensuring that inserted characters are non-repetitive or constrained to certain ranges.

help

常见问题

外企场景

继续练习

#1048 最长字符串链 #942 增减字符串匹配 #1178 猜字谜