10.正则表达式

给你一个字符串?s?和一个字符规律?p，请你来实现一个支持 ‘.‘?和?‘*‘?的正则表达式匹配。
‘.‘匹配任意单个字符
‘*‘匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。

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

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

动态规划

分析：

定义一个二维的 DP 数组，其中 dp[i][j] 表示 s前i个字符和p前j个字符是否 match(i,j是可以等于0的，因为*可以匹配0个字符)，然后有下面三种情况(*需要保证i>0&&j>1*)：
1.  P[i][j] = P[i - 1][j - 1], if p[j - 1] != ‘*‘ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.‘);
2.  P[i][j] = P[i][j - 2], if p[j - 1] == ‘*‘ and the pattern repeats for 0 times;
3.  P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.‘), if p[j - 1] == ‘*‘ and the pattern repeats for at least 1 times.

bool isMatch(string s, string p) {
	const int m = s.size();
	const int n = p.size();
	vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
	for (int i = 0; i <= m; ++i)
		for (int j = 0; j <= n; ++j) {
			if (i == 0 && j == 0)//j==0，i不等于0时dp[i][j]默认为false
				dp[i][j] = true;
			if (i == 1 && j == 1)
				dp[i][j] = s[i-1] == p[j-1]||p[j-1]==‘.‘;
			else if (i == 0 && j>1)
				dp[i][j] = dp[i][j - 2] && p[j-1] == ‘*‘;
			else if (i>0 && j>1) {//需要保证i>0&&j>1，因为数组下标会出现i-1，j-2
				if (p[j-1] != ‘*‘)
					dp[i][j] = dp[i - 1][j - 1] && (s[i-1] == p[j-1] || p[j-1] == ‘.‘);
				else
					dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i-1] == p[j - 2] || p[j - 2] == ‘.‘));
			}
		}
	return dp[m][n];
}

递归

大概思路如下：

- 若p为空，若s也为空，返回 true，反之返回 false。

- 若p的长度为1，若s长度也为1，且相同或是p为 ‘.‘ 则返回 true，反之返回 false。

- 若p的第二个字符不为*，若此时s为空返回 false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配。

- 若p的第二个字符为*，进行下列循环，条件是若s不为空且首字符匹配（包括 p[0] 为点），调用递归函数匹配s和去掉前两个字符的p（这样做的原因是假设此时的星号的作用是让前面的字符出现0次，验证是否匹配），若匹配返回 true，否则s去掉首字母（因为此时首字母匹配了，我们可以去掉s的首字母，而p由于星号的作用，可以有任意个首字母，所以不需要去掉），继续进行循环。

- 返回调用递归函数匹配s和去掉前两个字符的p的结果（这么做的原因是处理星号无法匹配的内容，比如 s="ab", p="a*b"，直接进入 while 循环后，我们发现 "ab" 和 "b" 不匹配，所以s变成 "b"，那么此时跳出循环后，就到最后的 return 来比较 "b" 和 "b" 了，返回 true。再举个例子，比如 s="", p="a*"，由于s为空，不会进入任何的 if 和 while，只能到最后的 return 来比较了，返回 true，正确）。

    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        //当n<2时单独处理
        if(n==0) return m==0;
        if(n==1) return m==1&&(s[0]==p[0]||p[0]==‘.‘);
        
        //当p[1]==‘*‘
        if(p[1]==‘*‘) {
            while(!s.empty()&&(s[0]==p[0]||p[0]==‘.‘)){//s可能为空
                //先按*匹配0字符试一次，因为可能出现例如s=“sp”，p=“s*sp”这种*可以匹配但不用匹配的情况
                if(isMatch(s,p.substr(2))) return true;
                s=s.substr(1);
            }
            return isMatch(s,p.substr(2));
        }
        //当p[1]!=‘*‘
        return !s.empty()&&(s[0]==p[0]||p[0]==‘.‘)&&isMatch(s.substr(1),p.substr(1));//s可能为空
    }

参考：https://www.cnblogs.com/grandyang/p/4461713.html

10.正则表达式

原文：https://www.cnblogs.com/Frank-Hong/p/13363255.html