题目链接：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)\)。