问题描述
题目链接 ‘.’ 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
问题分析
正则表达式匹配问题，首先要弄清楚问题里面的要求，总结下来正则式中会有以下四种类型的正则项：
算法构思
一开始没太理解.的意思走了弯路，钻了牛角，一直想从字符串两端向中部匹配，最后是.*XXX.的格局，按照这种设想在leetcode上测试给出了wrong answer的情况，问题是XXX有可能出现在字符串中不止1次！而我任性的取了它出现的“第一次”，所以会漏到一些情况，导致不能匹配。 后来想到解决这个问题一定是从前面到后面匹配的过程（思考多了就会有这种意识），关键在于怎么解决a* 和.* 类型的匹配，嗯，很简单（现在觉得╮(╯▽╰)╭），就是把所有可能的答案都作为候选集，举个例子：a 遇到aaa，有四种可能性：0匹配，a，aa，aaa，而*aaa 遇到aaa有三种可能：a，aa，aaa；.* 遇到bcd，有四种候补：0匹配，b，bc，bcd。
数据结构
问题来了,duang，duang，duang~ – 预处理正则表达式？ 将正则表达式的字符串预处理为上述四种类型的正则表达项 – 如何管理这些候补集呢？ 队列，，恩，每次出现新的匹配放入队列即可。 – 如何判断是否匹配成功呢？ 两种情况，一是待匹配字符串和正则表达式全部匹配结束，则一定是成功的；二是只有待匹配字符创匹配结束而正则表达式剩余项全都是a* or .* 类型的正则项。
代码
说明：刚开始用的vector存储的候补集，运行时间为73ms，后来改为数组的循环队列（注：这里没考虑队列满的情况，所以数组开的很大）后缩短至27ms，提升效果显著。。。
class Solution {public:*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;queue_i[tail_i;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 = 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;}}(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++;}(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;}}}(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;}};
人的一生是奋斗的一生，人们为了取得成功都在不断地努力着，
