题目描述
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
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".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
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".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
解题思路
题目意思很明确，给定一个正则表达式判断输入的字符串是否能与该表达式完全匹配。比较特殊的是，这个正则表达式中只有字母、小数点以及星号。
先来梳理一下这三种字符的意义。字母无需多解释：匹配和它自己一样的字符；小数点表示匹配任意字符；而*不单独使用，跟在字母或者小数点后，表示匹配0个到多个 * 前字符。
看起来像是一个最长递增字串之类的问题，即s的子串s'能匹配到p的子串p'，慢慢扩展这个s'的长度，看下是否能完全匹配。话虽如此，但状态转移还是比较复杂的过程，不妨先处理一下边界情况：
当正则串p的长度和s的长度都为0的时候，不需要考虑子串的问题，直接返回true；当p的长度为0而s的长度不为0时，返回false；当s的长度为0而p的长度不为0，考虑p是否可以匹配空串，即：p是否为a*b*....z*这样的结构，如果是则返回true，反之则返回false。
这样，边界情况就考虑完毕了，我们可以来设计状态转移方程了。假设s'能匹配到p'，则将p'的末尾位置的值设为true（同一个s'可以匹配到若干个p'）。假设s''比s'多一位，这时我们可以这样找p''：找到所有p'，对于任意一个p'，能不能加入后一个字符变成p''，并且让s''成功匹配。找到这样的p''之后，我们考虑p''是否为*结尾，若是*结尾，则将后续所有的a*b*...z*这样连续的结构上的*的位置都变为true；若不是，则找后续$a*b*...z*这样连续的结构上的 *置为true（因为a*可以匹配一个空串，即p''可以经过边到达的串也是可以匹配s''的）。重复进行这样的迭代，直到p'集合为空，这时退出并返回false（有一个字符无法在正则表达式中找到下一个匹配）；重复到s''==s时，返回p''最后一个位置上的值。
简单地说，这个算法其实是一个简化的NFA模型，即不停的加入字符串s中的字符，根据上次找到的状态集寻找这次迭代要找的状态集，当所有字符输入完毕，并存在一个状态是终止状态（p''最后一个位置上的值为true）时返回true，反之则返回false。需要注意的是，由于正则中有*的存在，它会让匹配到的新状态自动跳转到别的状态（即NFA中的边），使状态数增加。
这次用的算法其实跟NFA比较相似，使用动态规划递归的算法可以让题目变得更加简单，详情可以参考Leetcode中的solution以及大家的discussion。
时间复杂度分析
遍历整个字符串s（长度为sl），正则表达式长度为pl，每个字符最多对应pl个状态，因此复杂度为O(pl * sl)。
空间复杂度分析
由状态数决定O(pl * sl)，可以适当优化。
源码
class Solution {
public:
bool isMatch(string s, string p) {
if (p.length() == 0 && s.length() == 0) {
return true;
}
if (p.length() == 0) {
return false;
}
if (s.length() == 0) {
for (int i = 0; i < p.length(); ++i) {
if (p[i] != '*' && i + 1 < p.length() && p[i + 1] != '*') {
return false;
} else if (p[i] != '*' && i + 1 == p.length()) {
return false;
}
}
return true;
}
if (p.length() == 1) {
return (p[0] =='.' || p[0] == s[0]) && s.length() == 1;
}
int dp[100][100] = {0};
for (int j = 0; j < s.length(); ++j) {
for (int i = 0; i < p.length(); ++i) {
dp[0][i] = 0;
}
}
for (int i = 0; i < p.length(); ++i) {
if (p[i] == '*') {
dp[0][i] = 1;
continue;
} else {
if (i != p.length() - 1) {
if (p[i + 1] == '*') {
dp[0][i + 1] = 1;
} else {
dp[0][i] = (p[i] == s[0] || p[i] == '.');
if (dp[0][i]) {
int j = i + 2;
while (j < p.length()) {
if (p[j] == '*') {
dp[0][j] = 1;
j += 2;
} else {
break;
}
}
j = i + 1;
if (p[j] == '*') {
while (j < p.length()) {
if (p[j] == '*') {
dp[0][j] = 1;
j += 2;
} else {
break;
}
}
}
}
break;
}
if (p[i] == s[0] || p[i] == '.') {
dp[0][i] = 1;
if (dp[0][i]) {
int j = i + 2;
while (j < p.length()) {
if (p[j] == '*') {
dp[0][j] = 1;
j += 2;
} else {
break;
}
}
j = i + 1;
if (p[j] == '*') {
while (j < p.length()) {
if (p[j] == '*') {
dp[0][j] = 1;
j += 2;
} else {
break;
}
}
}
}
}
} else {
dp[0][i] = (p[i] == s[0] || p[i] == '.');
}
}
}
for (int i = 1; i < s.length(); ++i) {
char target = s[i];
bool flag = false;
for (int j = 0; j < p.length(); ++j) {
if (dp[i - 1][j] == 1 && j != p.length() - 1) {
if (p[j + 1] == '.' || p[j + 1] == s[i]) {
dp[i][j + 1] = 1;
if (j + 2 < p.length() && p[j + 2] == '*') {
dp[i][j + 2] = 1;
int next = j + 2 + 2;
while (next < p.length()) {
if (p[next] == '*') {
dp[i][next] = 1;
next += 2;
} else {
break;
}
}
}
int next = j + 1 + 2;
while (next < p.length()) {
if (p[next] == '*') {
dp[i][next] = 1;
next += 2;
} else {
break;
}
}
flag = true;
} else if ((p[j] == '.' || p[j] == s[i]) && j < p.length() - 1 && p[j + 1] == '*') {
flag = true;
dp[i][j] = 1;
dp[i][j + 1] = 1;
int next = j + 1 + 2;
while (next < p.length()) {
if (p[next] == '*') {
dp[i][next] = 1;
next += 2;
} else {
break;
}
}
}
}
}
if (!flag) {
return false;
}
}
return dp[s.length() - 1][p.length() - 1];
}
};
