【双指针】B022

如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）

给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。

输入：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".

提示：

1 <= queries.length <= 100 1 <= queries[i].length <= 100 1 <= pattern.length <= 100 所有字符串都仅由大写和小写英文字母组成。

二、Solution

方法一：双指针

思路

我们遍历两个串时，会有以下几种情况：

q[i] = p[j] 时，证明两个串都是大写字母的开头q[i] != p[j] 时，如果 q[i] 是小写，那么当没事发生；如果 q[i] 是大写，这种情况就是不匹配

当遍历完毕后（两个串之一遍历完），如果是模式串 p 没有遍历完，证明不匹配；而如果查询串 q 还有大写字母证明也不匹配

class Solution { boolean isMatch(char[] q, char[] p) { int i = 0, j = 0, n = q.length, m = p.length; while (i < n && j < m) { if (q[i] == p[j]) { i++; j++; } else { if ('A' <= q[i] && q[i] <= 'Z') return false; i++; } } if (j != m) return false; while (i < n) { if ('A' <= q[i] && q[i] <= 'Z') return false; i++; } return true; } public List<Boolean> camelMatch(String[] qs, String pattern) { List<Boolean> ans = new LinkedList<>(); char[] p = pattern.toCharArray(); for (String q : qs) { ans.add(isMatch(q.toCharArray(), p)); } return ans; } }

复杂度分析

时间复杂度：$O(N\times m)$，N 为查询串的总字符个数，m 为模式串的长度空间复杂度：$O(n)$，