Medium

题目描述

给你一个字符串数组 queries 和一个字符串 pattern，返回一个布尔数组 answer，其中 answer[i] 是 true 当且仅当 queries[i] 匹配 pattern。

如果可以在 pattern 中插入小写英文字母使其等于查询字符串 queries[i]，那么查询字符串匹配模式。你可以在 pattern 的任何位置插入字符，也可以选择不插入任何字符。

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

解题思路

这道题的核心是理解驼峰式匹配的规则：我们可以在模式串中的任意位置插入小写字母，但不能插入大写字母。

解题思路：

对于每个查询字符串，我们使用双指针方法来判断是否匹配模式串：

  1. 字符匹配策略：

    • 如果当前字符相等（无论大小写），两个指针都向前移动
    • 如果查询串当前字符是小写字母而模式串字符不匹配，只移动查询串指针（相当于跳过这个小写字母）
    • 如果查询串当前字符是大写字母但与模式串不匹配，直接返回 false

  2. 终止条件：

    • 模式串遍历完成后，查询串剩余的字符必须全部是小写字母
    • 查询串遍历完成但模式串还有字符，返回 false

这种方法的时间复杂度为 O(n×m)，其中 n 是查询数组长度，m 是平均字符串长度。空间复杂度为 O(1)（不考虑结果数组）。

该算法简洁高效，一次遍历即可完成匹配判断，是最优解法。

代码实现

class Solution {
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> result;
        for (const string& query : queries) {
            result.push_back(isMatch(query, pattern));
        }
        return result;
    }
    
private:
    bool isMatch(const string& query, const string& pattern) {
        int i = 0, j = 0;
        int m = query.length(), n = pattern.length();
        
        while (i < m && j < n) {
            if (query[i] == pattern[j]) {
                i++;
                j++;
            } else if (islower(query[i])) {
                i++;
            } else {
                return false;
            }
        }
        
        // 检查模式串是否完全匹配
        if (j < n) return false;
        
        // 检查查询串剩余字符是否都是小写字母
        while (i < m) {
            if (isupper(query[i])) return false;
            i++;
        }
        
        return true;
    }
};

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        def is_match(query, pattern):
            i = j = 0
            m, n = len(query), len(pattern)
            
            while i < m and j < n:
                if query[i] == pattern[j]:
                    i += 1
                    j += 1
                elif query[i].islower():
                    i += 1
                else:
                    return False
            
            # 检查模式串是否完全匹配
            if j < n:
                return False
            
            # 检查查询串剩余字符是否都是小写字母
            while i < m:
                if query[i].isupper():
                    return False
                i += 1
            
            return True
        
        return [is_match(query, pattern) for query in queries]

public class Solution {
    public IList<bool> CamelMatch(string[] queries, string pattern) {
        List<bool> result = new List<bool>();
        foreach (string query in queries) {
            result.Add(IsMatch(query, pattern));
        }
        return result;
    }
    
    private bool IsMatch(string query, string pattern) {
        int i = 0, j = 0;
        int m = query.Length, n = pattern.Length;
        
        while (i < m && j < n) {
            if (query[i] == pattern[j]) {
                i++;
                j++;
            } else if (char.IsLower(query[i])) {
                i++;
            } else {
                return false;
            }
        }
        
        // 检查模式串是否完全匹配
        if (j < n) return false;
        
        // 检查查询串剩余字符是否都是小写字母
        while (i < m) {
            if (char.IsUpper(query[i])) return false;
            i++;
        }
        
        return true;
    }
}

/**
 * @param {string[]} queries
 * @param {string} pattern
 * @return {boolean[]}
 */
var camelMatch = function(queries, pattern) {
    return queries.map(query => {
        let i = 0, j = 0;
        
        while (i < query.length && j < pattern.length) {
            if (query[i] === pattern[j]) {
                i++;
                j++;
            } else if (query[i] >= 'a' && query[i] <= 'z') {
                i++;
            } else {
                return false;
            }
        }
        
        while (i < query.length) {
            if (query[i] >= 'A' && query[i] <= 'Z') {
                return false;
            }
            i++;
        }
        
        return j === pattern.length;
    });
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m)，其中 n 是 queries 数组长度，m 是平均字符串长度
空间复杂度O(1)，只使用常数额外空间（不考虑结果数组）