LeetCode: 正则表达式匹配

  工作快半年了，好久没上leetcode做题，前几天在知乎上看到一个leetcode的一个题有效数字，大概内容是判断字符串是否是可以用十进制来表示的数字，了解到了一种对我来说没学过的知识，即，正则表达式是可以用状态机(自动机)去表示的(<<编译原理>>相关的书籍似乎都有介绍)，而自动机又分NFA与DFA…啪啦啪啦，总之就是了解到了很多东西，然后就想起了这道我以前没解决的题…

题目简介：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:

输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:

输入:
s = “ab”
p = “."
输出: true
解释: ".” 表示可匹配零个或多个（’*’）任意字符（’.’）。
示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:

输入:
s = “mississippi”
p = “misisp*.”
输出: false

题解:

  解题方法为暴力匹配。
  思路：需要去匹配的字符串为S，正则表达式为P，那么考虑以下情况(i=0~S.length-1,j=0~P.length-1):
  1、什么情况下才能判定两者完全匹配，因为是暴力搜索，我使用递归去迭代，所以我要知道终止条件是什么(以前就是没弄清楚这个，所以没解题），在假设P为一个有效的正则表达式情况下，当S[i]==P[j](这里的意思为，字符串S:0~i与表达式P:0~j匹配)，我们要判断其是否完全匹配，就要看j是否为终点，那什么是终点呢，如S=aaa,P=a*a,那么P[2](下标为2)就为终点，又如S=aaa,P=a*，那么P[0]为终点，因为*可以匹配0或者任意多个a，所以不把*算进终点。
  2、分析暴力搜索情况，这里详情看代码吧。
  3、暴力搜索难免会重复搜索，考虑记录搜索的情况，去重。
  4、做完以上步骤，还可以看出其动态规划的最优子结构，从而用动态规划去做，能够优化性能及其效率，这里我就懒得做了…

class Solution {
public:
	unordered_set<int> endp;
	int **ary;
	bool isMatch(string s, string p) {
		int plen = p.length() - 1;
        int pblen=plen;
		while (plen >= 0) {
			if (p[plen] == '*') {
				endp.insert(plen-1);
				plen -= 2;
				if (plen >= 0 && p[plen] != '*') {
					endp.insert(plen+1);
					break;
				}
			}
			else {
				if (plen == pblen) {
					endp.insert(plen + 1);
				}
				else {
					endp.insert(plen);
				}
				break;
			}
		}
		if (s == "") {
			if (endp.find(0) != endp.end()||s==p)
				return true;
			else
				return false;
		}
		ary = new int*[s.length()];
		for (int i = 0; i < s.length(); i++) {
			ary[i] = new int[p.length()];
		}
		auto r = func(s, p);
		for (int i = 0; i < s.length(); i++) {
			for (int j = 0; j < p.length(); j++) {
				ary[i][j] = 0;
			}
		}
        for (int i = 0; i < s.length(); i++) {
			delete[] ary[i];
		}
		delete[] ary;
		return r;
	}

	bool func(string &s, string &p, int si = 0, int pi = 0) {
		if (si == s.length()) {
			if (endp.find(pi) != endp.end())
				return true;
			else
				return false;
		}
		if (pi == p.length())
			return false;
		if (ary[si][pi] == 1)
			return true;
		else if (ary[si][pi] == 2)
			return false;
		bool ret = false;
		bool cur;
		if (s[si] == p[pi] || p[pi] == '.') {
			cur = true;
		}
		else {
			cur = false;
		}
		if (cur) {
			if (pi + 1 < p.length() && p[pi + 1] == '*') {
				ret=func(s, p, si + 1, pi) || func(s, p, si + 1, pi + 2) || func(s, p, si, pi + 2);
			}
			else {
				ret = func(s, p, si + 1, pi + 1);
			}
		}
		else {
			if (pi + 1 < p.length() && p[pi + 1] == '*') {
				ret=func(s, p, si, pi + 2);
			}
			else {
				ret = false;
			}
		}
		if (ret) {
			ary[si][pi] = 1;
		}
		else {
			ary[si][pi] = 2;
		}
		return ret;
	}
};