LeetCode 1023.驼峰式匹配

给你一个字符串数组 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 由英文字母组成

对于每一个查询query，与pattern进行双序列双指针，跳过query中有，pattern中没有的小写字母：

class Solution {
public:vector<bool> camelMatch(vector<string>& queries, string pattern) {vector<bool> ans(queries.size());for (int i = 0; i < queries.size(); ++i) {int queryIdx = 0;int patternIdx = 0;string &query = queries[i];bool flag = true;while (queryIdx < query.size() && patternIdx < pattern.size()) {// 如果查询和pattern里的字符相同，则同时右移指针if (query[queryIdx] == pattern[patternIdx]) {++queryIdx;++patternIdx;// 否则，如果查询里的字符是小写，则可以填充到pattern中，右移查询指针} else if (islower(query[queryIdx])) {++queryIdx;// 如果查询和pattern里的字符不同，且当前查询的字符不是能填充到pattern中的小写// 则一定不能匹配} else {flag = false;break;}}// 可能查询还未完成，此时需要检查查询中是否还有大写// 如果有大写，由于大写不能填充到pattern中，则一定不匹配while (queryIdx < query.size()) {if (isupper(query[queryIdx])) {flag = false;break;}++queryIdx;}// 如果query匹配完没有问题，且pattern也遍历完，就说明可以匹配到// pattern必须要遍历完，因为pattern不能多出来，多出来的部分不能变没ans[i] = flag && patternIdx == pattern.size();}return ans;}
};

如果queries的长度为n，其中每一个查询的平均长度为m，则此算法时间复杂度为O(nm)，空间复杂度为O(1)。