当前位置：首页 > article >正文

LeetCode每日一题 1023. 驼峰式匹配 --双指针

article 2024/9/19 23:57:43

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

题目:1023. 驼峰式匹配

题解:

代码实现:

完结撒花:

题目:1023. 驼峰式匹配

题解:

本题挺容易想到的,难得是如何处理特殊的情况.

题目的大意是:

模板串以每一个大写字母为分割,组成一个个子串.这些子串需要在待查询项中出现一次.且待查询串中不能再出现除此之外以大写字母开头的"子串".

例如以下这种情况:

拆分成:F+B

只要待查询项中含有F+B的组成格式且不含有其他大写字母即可作为true.其余需要填入false

再例如以下这种情况:

FoBa可以拆分为:Fo+Ba 只要一个个去对比待查询项中是否含有这些子串内容即可.

总结上面的情况:我们不难发现,这是用一个双指针的方法去对比每一个待查询项.

我们先模拟一下这个过程:

一个指针指向queries,一个指针指向pattern.

若有相同的则同时向前位移一格

出现不同的需要判断一下,是否为大写字母.若有queries中的大写字母与pattern中的字母不同.则直接填入false即可.

若对比完发现,指向pattern的指针仍然没有走到底,说明pattern在queries中并未全部出现,则同样填入false.

梳理完了整个流程,接下来我们来看看代码实现.

首先创建一个长度为queries.size()的vector数组,其中填满true

之后依次遍历每一个queries的,将其与pattern进行比较.复现上面的过程

代码实现:

#include<vector>
#include<string>
#include<iostream>
using namespace std;
class Solution {
public:
vector<bool> camelMatch(vector<string>& queries, string pattern) {
vector<bool>ans(queries.size(),true);
int npat=pattern.size();
for(int i=0;i<queries.size();i++)
{

int p=0;
for(auto c:queries[i])
{
if(pattern[p]==c)
{
p++;
}
else if(isupper(c))
{
ans[i]=false;
}
}
if(p<pattern.size())
ans[i]=false;

}

return ans;
}
};