leetcode010:Regular Expression Matching
问题描述题目链接 The matching should cover the entire input string (not partial). The function prototype should be: Some examples: 问题分析正则表达式匹配问题,首先要弄清楚问题里面的要求,总结下来正则式中会有以下四种类型的正则项:
算法构思一开始没太理解.的意思走了弯路,钻了牛角,一直想从字符串两端向中部匹配,最后是.*XXX.的格局,按照这种设想在leetcode上测试给出了wrong answer的情况,问题是XXX有可能出现在字符串中不止1次!而我任性的取了它出现的“第一次”,所以会漏到一些情况,导致不能匹配。 数据结构问题来了,duang,duang,duang~ 代码说明:刚开始用的vector存储的候补集,运行时间为73ms,后来改为数组的循环队列(注:这里没考虑队列满的情况,所以数组开的很大)后缩短至27ms,提升效果显著。。。 class Solution {
public:
bool isMatch(const char *s,const char *p) {
int slen = strlen(s);
int plen = strlen(p);
int alen = 0;
int i = 0,j = 0;
int count_p_single = 0;
string *arr = new string[plen];
//预处理正则表达式
while (i < plen){
if (i + 1 < plen&&p[i + 1] == '*'){
arr[alen] += p[i];
arr[alen] += p[i + 1];
i = i + 2;
}
else{
arr[alen] += p[i];
i++;
count_p_single++;
}
alen++;
}
//vector<int> vec_i; //i在字符串s上的所有当前候选位置
//vector<int> vec_j; //j在字符串arr上的所有当前候选位置
i = j = 0;
//vec_i.push_back(i);
//vec_j.push_back(j);
int queue_i[100000]; //i在字符串s上的所有当前候选位置
int queue_j[100000]; //j在字符串arr上的所有当前候选位置
int tail_i; //队尾,进队操作
int head_i; //对头,出队操作
int tail_j;
int head_j;
tail_i = tail_j = head_i = head_j = 0;
queue_i[tail_i++ % 100000] = 0;
queue_j[tail_j++ % 100000] = 0;
//while (vec_i.size() > 0){
while (head_i % 100000 != tail_i % 100000){
//i = vec_i.back();
//j = vec_j.back();
//vec_i.pop_back();
//vec_j.pop_back();
i = queue_i[head_i++ % 100000];
j = queue_j[head_j++ % 100000];
if (i == slen && j == alen) return true;
if (i == slen && j<alen) {
int flag = 0;
for (int k = j; k < alen; k++)
if (arr[k].length() == 1) flag = 1;
if (!flag)
return true;
}
if (i >= slen || j >= alen || slen-i < count_p_single) continue;
//情况1:a 或 .
if (arr[j].length() == 1){
if (arr[j][0] == s[i] || arr[j][0] == '.'){
i++; j++;
//vec_i.push_back(i);
//vec_j.push_back(j);
queue_i[tail_i++ % 100000] = i;
queue_j[tail_j++ % 100000] = j;
count_p_single--;
}
else
{
continue;
}
}
//情况2:a*
else if (arr[j].length() == 2 && arr[j][0] != '.'){
//vec_i.push_back(i);
//vec_j.push_back(j + 1);
queue_i[tail_i++ % 100000] = i;
queue_j[tail_j++ % 100000] = j + 1;
if(arr[j][0]==s[i]){
char goal = s[i];
int counts = 0,counta = 0;
while (i < slen&&s[i] == goal) {
counts++;
i++;
}
while (j < alen&&arr[j][0] == goal){
if (arr[j].length() == 1)
counta++;
j++;
}
//aaa 3
//a*aa* 1 3>=1
if (counta > counts) continue;
for (int x = counta; x <= counts; x++){
//vec_i.push_back(i-counts+x);
//vec_j.push_back(j);
queue_i[tail_i++ % 100000] = i - counts + x;
queue_j[tail_j++ % 100000] = j;
}
}
}
//情况3:.*
else if (arr[j].length() == 2 && arr[j][0] == '.'){
if (alen - 1 - j <= 0) return true;
j = j + 1;
for (int m = i; m <= slen; m++){
//vec_i.push_back(m);
//vec_j.push_back(j);
queue_i[tail_i++ % 100000] = m;
queue_j[tail_j++ % 100000] = j;
}
}
}
return false;
}
};
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |