10. 正则表达式匹配

[MyLinChi]

题目描述

给你一个字符串 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

解法1（递归法）：

由于*前面的字符可以匹配任意次（包括0次），所以不能使用两个分别指向s和p的指针单次移动完成匹配，涉及到分叉的问题，自然想到递归。递归的伪代码大致如下：

bool isMatch(string s, string p) {
    if p is NULL
        return s==NULL;
    if p[1] is '*'
        if p[0]匹配0次 && isMatch(s.substr(1),p)
           || p[0]匹配1次 && isMatch(s,p.substr(1))
               return true;
        else
               return false;
    else if p[0]匹配1次 && isMatch(s.substr(1),p.substr(1))
        return true
    else
        return false

写成代码是

class Solution {
public:
	bool isMatch(string s, string p) {
		if (p.empty())
			return s.empty();
		if (p.length() > 1 && p[1] == '*'){
			if (isMatch(s, p.substr(2))
				|| (!s.empty() && (s[0] == p[0]||p[0]=='.') && isMatch(s.substr(1), p)))
				return true;
			else
				return false;
		}
		else if (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1)))
			return true;
		else
			return false;
	}
};

解法2（动态规划）：

设动态规划矩阵为K，是一个mxn大小的矩阵，其中m=s.length(),n=p.length()。K[i,j]表示字符串s[0,i)与p[0,j)是否匹配，由于二者都是空串时是匹配的，故K(0,0)=1。

I 这种情况是根据i，j的取值情况来分类的，由于情况较多，所以分类复杂。

class Solution {
public:
	bool isMatch(string s, string p) {
		const int maxM = 100;
		const int maxN = 100;
		char K[maxM][maxN];
		int m = s.length();
		int n = p.length();
		for (int i = 0; i <= m;i++)
		for (int j = 0; j <= n; j++){
			if (i == 0 && j== 0){
				K[i][j] = 1;
			}
			else if(i != 0 && j== 0){
				K[i][j] = 0;
			}
			else if (i == 0 && j != 0){
				if (j == 1){
					K[i][j] = 0;
				}else{ //j>= 2
					if (p[j - 1] == '*'){
						K[i][j] = K[i][j - 2];
					}
					else
						K[i][j] = 0;
				}
			}
			else{
				if (j == 1){
					if (i == 1)
						K[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '.');
					else
						K[i][j] = 0;
				}
				else{
					if (p[j - 1] == '*'){
						K[i][j] = K[i][j - 2]==1 || (K[i - 1][j] && (s[i - 1] == p[j - 2]||p[j-2]=='.'));
					}
					else
						K[i][j] = K[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
				}
			}
		}
		return K[m][n] == 1;
	}
};

II 这种情况是根据当前计算的p的最右端的元素是否为'*'（此时要求p的长度>= 2,即j>2）来分类的，这种情况下代码篇幅明显缩短，但是运行时间和占用内存是一样的

class Solution {
public:
	bool isMatch(string s, string p) {
		const int maxM = 100;
		const int maxN = 100;
		bool K[maxM][maxN];
		int m = s.length();
		int n = p.length();
		memset(K, false, maxM*maxN);
		K[0][0] = true;
		for (int i = 0; i <= m; i++)
		for (int j = 1; j <= n; j++){
			if (j>1 && p[j - 1] == '*'){
				K[i][j] = K[i][j - 2] || ((i>0) && K[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
			}
			else{
				K[i][j] = (i > 0) && K[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
			}
		}
		return K[m][n];
	}
};

动态规划

class Solution {
public:
    bool isMatch(string s, string p) {
        if (s.size() != 0 && p.size() == 0)return false;
        if (s.size() == 0 && p.size() == 0)return true;

        vector<vector<bool>> dp = vector<vector<bool>>(s.size() + 1, vector<bool>(p.size() + 1, false));
        for (int i = 0; i <= s.size(); ++i) {
            for (int j = 0; j <= p.size(); ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                }
                else if (i != 0 && j == 0) {
                    dp[i][j] = false;
                }
                else if (i == 0 && j != 0) {
                    dp[i][j] = (j > 1) && dp[i][j - 2] && p[j - 1] == '*' && p[j - 2] != '*';
                }
                else {
                    if ('.' == p[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    else if ('*' == p[j - 1] && j > 1) {
                        dp[i][j] = dp[i][j - 2];
                        for (int k = i - 1; k >= 0 && (s[k] == p[j - 2] || p[j-2]=='.'); --k)
                            if (dp[k][j - 2]) { dp[i][j] = true; break; }
                    }
                    else {
                        dp[i][j] = dp[i - 1][j - 1] && s[i - 1] == p[j - 1];
                    }
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};