1023. 驼峰式匹配

题目链接：1023. 驼峰式匹配

方法：双指针

解题思路

• 对于当前询问 \(query\) 和 模式串 \(pattern\)，初始化两个指针分别指向起始位置。
• 若两个字符相同则都右移一位；否则判断当前 \(query\) 对应的字符是否为大写字母，若是则返回 \(false\)，否则其指针右移一位；若有一个指针到达结尾，则结束循环。
• 若循环结束时，\(pattern\) 的指针未遍历完，则说明没有不能得到 \(query\)，返回 \(false\)；否则若 \(query\) 指针未遍历完，则继续判断剩余字符是否为大写字母，若是则返回false；
• 最后返回 \(true\)。

代码

class Solution {
public:
    bool check(string query, string pattern) {
        int n = query.length(), m = pattern.length();
        int idx1 = 0, idx2 = 0;
        while (idx1 < n && idx2 < m) {
            if (query[idx1] == pattern[idx2]) {
                idx1 ++ ; idx2 ++ ;
            } else {
                if (query[idx1] >= 'A' && query[idx1] <= 'Z') return false;
                else idx1 ++ ;
            }
        }
        if (idx2 < m) return false;
        while (idx1 < n) {
            if (query[idx1] >= 'A' && query[idx1] <= 'Z') return false;
            idx1 ++ ;
        }
        return true;
    }
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        int n = queries.size();
        vector<bool> ans(n);
        for (int i = 0; i < n; i ++ ) {
            ans[i] = check(queries[i], pattern);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(nm)\)，\(n\) 为询问数组的长度，\(m\) 为当前询问的长度；
空间复杂度：\(O(1)\)。