问题描述

题目链接
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s,const char *p)

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”,“a*”) → true
isMatch(“aa”,“.*”) → true
isMatch(“ab”,“.*”) → true
isMatch(“aab”,“c*a*b”) → true

问题分析

正则表达式匹配问题，首先要弄清楚问题里面的要求，总结下来正则式中会有以下四种类型的正则项：

1. a型，单个字母，正常匹配，1对1；
2. a*型，匹配0到n个重复字母(a*)，视情况而定；
3. .型，匹配任意1个字母；
4. .*型，屌爆存在，想咋匹配自便！

算法构思

一开始没太理解.的意思走了弯路，钻了牛角，一直想从字符串两端向中部匹配，最后是.*XXX.的格局，按照这种设想在leetcode上测试给出了wrong answer的情况，问题是XXX有可能出现在字符串中不止1次！而我任性的取了它出现的“第一次”，所以会漏到一些情况，导致不能匹配。
后来想到解决这个问题一定是从前面到后面匹配的过程（思考多了就会有这种意识），关键在于怎么解决a* 和.* 类型的匹配，嗯，很简单（现在觉得╮(╯▽╰)╭），就是把所有可能的答案都作为候选集，举个例子：正则项a* 遇到aaa，有四种可能的匹配：0匹配、a、aa、aaa，而a*aa* 遇到aaa有三种可能：a、aa、aaa；.* 遇到bcd，有四种候补：0匹配、b、bc、bcd。

数据结构

问题来了,duang，duang，duang~
- 预处理正则表达式？
将正则表达式的字符串预处理为上述四种类型的正则表达项
- 如何管理这些候补集呢？
队列，恩，每次出现新的匹配放入队列即可。
- 如何判断是否匹配成功呢？
两种情况：
一是待匹配字符串和正则表达式全部匹配结束，则一定是成功的；
二是只有待匹配字符创匹配结束而正则表达式剩余项全都是a* or .* 类型的正则项。

代码

说明：刚开始用的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;
    }
};