动态规划<2>正则表达式匹配(regular-expression-matching)

vlambda
2020-05-14

动态规划<2>正则表达式匹配(regular-expression-matching)

本节为动态规划第二题：正则表达式匹配(regular-expression-matching)，主要包括：问题描述，算法思路，复杂度分析，C++实现。

1. 问题描述

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

2. 解法

2.1 回溯算法

当模式串的第i个元素的下一个元素是星号时，会有两种情况：

1）i元素在匹配串中出现0次，我们就保持s不变，将p减掉两个元素，调用isMatch。例如：匹配串bc，模式串a*bc。

2）i元素在匹配串出现一次或多次，先比较i元素和匹配串首元素，相等则保持模式串不变，减掉s的首元素，调用isMatch。例如匹配串aabb，模式串abb。

但是会有一种特殊的情况，例如匹配串abb，模式串aabb。这种情况应该是匹配的，但是按照我们设想的两种情况应该是属于第二种情况，所以算法不会判断属于那种情况，而是将两种情况都运行一遍。

该算法C++代码如下：

//1.回溯算法 bool isMatch(string s, string p) { if (p.empty()) return s.empty(); bool first_match = (!s.empty() && (p.at(0) == s.at(0) || p.at(0) == '.')); if (p.length() >= 2 && p.at(1) == '*') { return (isMatch(s, p.substr(2, p.length() - 2)) || (first_match && isMatch(s.substr(1, s.length() - 1), p))); } else { return(first_match && isMatch(s.substr(1, s.length() - 1), p.substr(1, p.length() - 1))); } }

2.2 动态规划

我们令dp[i][j]表示s的前i个元素是否可以被p的前j个元素所匹配，于是有：

1）dp[0][0]为true，dp[0][1]为false，dp[][0]这一列为false

2）dp数组大小为dp[s.length+1][p.length+1]

C++代码如下：

bool headMatched(string s, string p, int i, int j) { return s.at(i) == p.at(j) || p.at(j) == '.'; } bool isMatch(string s, string p) { vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1)); //初始化，false隐式成立 dp[0][0] = true; //填写第一行也就是dp[0][2]~dp[0][p.length()] for (int k = 2; k <= p.length(); k++) { //p字符串的第2个字符是否等于*，此时j元素仍为0个，所以s不变，p减除两个字符 dp[0][k] = p.at(k - 1) == '*' && dp[0][k - 2]; } //dp数组剩余部分填写 for (int i = 0; i < s.length(); i++) { for (int j = 0; j < p.length(); j++) { //p的第j个字符是否为* if (p.at(j) == '*') { //1.s不变，p移除两个元素 //2.s[i]与p[j-1]相等，p不变，s移除s[i] dp[i + 1][j + 1] = dp[i + 1][j - 1] || (dp[i][j + 1] && headMatched(s, p, i, j - 1)); } else { //s[i]和p[j]相等，移除s[i]和p[j] dp[i + 1][j + 1] = dp[i][j] && headMatched(s, p, i, j); } } } return dp[s.length()][p.length()]; }