LeetCode_10: Regular Expression Matching

# 引言

题目链接：https://leetcode.com/problems/regular-expression-matching/description/

# 题目大意

给定一个输入字符, 和一个匹配模式p, 实现正则表达式的匹配, 匹配模式支持'.'和'*'

'.' 匹配任何单个的字符

'*' 匹配前一个元素n次(n>=0)

要求模式p的匹配覆盖整个输入字符串, 而不是部分匹配

• Example

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

# 题解

# 方法一：递归求解

由于 * 在模式匹配中可以匹配前一个字符0或者多次, 稍后单独讨论, 先思考只有.的情况

1. 递归返回条件： 模式串 p 为空, 当p为空时,返回当前串是否为空即可
2. 在不考虑 *时, 匹配按位进行, 由s和p当前位置的相等性决定整体相等性, 即当前比对达成条件s[0] == p[0] || p[0] == '.'即可, 此时将s和p的当前字符一同去掉递归调用即可, 达到递归返回条件后返回堆栈结果

接下来考虑带有 * 的情况

将上述条件2作为默认条件判断入口, 依据*的定义其对于匹配的影响受到模式串当前位置前一个位置的影响, 带*号判断入口如下p.size() > 1 && p[1] == '*'

考虑一下两种情况：

1. *前模式串字符和当前匹配字符不相等：此时只有当前匹配字符匹配零次可以确保匹配继续下去, 否则直接失败, 此时模式串p前进两位即isMatch(s, p.substr(2))
2. *前模式串字符和当前匹配字符相等: 即*前模式串字符和当前匹配字符满足条件s[0] == p[0] || p[0] == '.',此时可以匹配当前s字符0次或多次, 0次匹配和第一种情况状态重复参考1即可.关于多次匹配拆分为多个一次匹配递归调用即可, 当进行一次匹配, 默认s前进一个字符, 模式串不进行位移递归准备下一次匹配即isMatch(s.substr(1), p), 当递归达成条件1时, 当前*号匹配完成

# 方法二：动态规划

当匹配串s和模式串p匹配完成时, 最后一次匹配所得结果和之前所有匹配整体结果共同决定匹配是否达成, 即当前匹配后整体结果是本地匹配在之前状态上的叠加, 因此我们可以同步不断缩减这个状态叠加过程达到简化问题规模的目的。

对于s和p, 作如下设定, s的最后一个字符为x, p的最后两个字符为yz(由于*号的匹配需要前一个字符共同作用), === 代表状态匹配

s = s'x
p = p'yz

下面开始分析

1. z != '*'
   1. 如果x===z (x==z || z=='.'),若s'===p'y, 则s===p
2. z == '*'(此时结合y一同考虑)
   1. x != y, 则yz共同决定匹配x零次, 若s'===p', 则s===p
   2. x == z, 此时考虑yz匹配x的次数
      1. 匹配0次：即yz跳过, 若s'x===p', 则s===p
      2. 匹配1次：即yz匹配x, 若s'===p', 则s===p
      3. 匹配多次：yz反复利用继续匹配, 若s'===p'yz', 则s===p

设定 dp[i][j] 表示 s[0,i) 和 p[0,j) 是否匹配

则分析对应dp方程如下：

if s[i - 1] == p[j - 1] || p[j - 1] == '.'
    dp[i][j] = dp[i - 1][j - 1];
 if (p[j - 1] == '*')
    // match 0,1,more
     dp[i][j] = dp[i][j - 2];
     dp[i][j] = dp[i - 1][j - 2];
     dp[i][j] = dp[i - 1][j];

复杂度 O(m*n), 递归进行堆栈调用时中间状态会有重复计算, 时间上相对耗时更多

# AC代码

c++ 递归版本

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

c++ dp版本

class Solution
{
  public:
    bool isMatch(string s, string p)
    {
        int lens = s.length();
        int lenp = p.length();
        bool dp[1001][1001];
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for (int i = 0; i <= lens; ++i)
        {
            for (int j = 1; j <= lenp; ++j)
            {
                if (i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    if (p[j - 1] == '*')
                    {
                        // match 0.1.more
                        dp[i][j] = dp[i][j - 2]
                        || (i > 0 && j > 1 && dp[i - 1][j - 2] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))
                        || (i > 0 && j > 1 && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                    }
                }
            }
        }
        return dp[lens][lenp];
    }
};

go版本

func isMatch(s string, p string) bool {
	lens, lenp := len(s), len(p)
	var dp[1001][1001] bool
	dp[0][0] = true
	for i := 0; i <= lens; i++ {
		for j := 1; j <= lenp; j++ {
			if i > 0 && (s[i-1] == p[j-1] || p[j-1] == '.') {
				dp[i][j] = dp[i-1][j-1]
			} else{
				if j > 1 && p[j-1] == '*' {
					dp[i][j] = dp[i][j-2] ||
							(i > 0 && dp[i - 1][j - 2] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) ||
							(i > 0 && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))
				}
			}
		}
	}
	return dp[lens][lenp]
}