前言
有多种解法
正文
问题来源
本问题来自leetcode上的10题。对应lintcode154题
问题描述
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。示例 2:
输入: s = "aa" p = "a*" 输出: true 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。示例 3:
输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。示例 4:
输入: s = "aab" p = "c*a*b" 输出: true 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。分析：
其中p[i]==’.’的情况可以和p[i]==s[j]的情况可以视为一体。所以本题最为主要的是p[i]==’‘情况下的讨论。 我们以s = “aab”，p = “ca*b”为例进行讨论
| i/j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 |
P[i][j] = P[i - 1][j - 1], if p[j - 1] != ‘’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.’);
P[i][j] = P[i][j - 2], if p[j - 1] == ‘’ and the pattern repeats for 0 times;
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.
C代码如下：
bool isMatch(char* s, char* p) {
int sl;
int pl;
int i,j;
bool **dp = NULL;
bool ret;
sl = strlen(s);
pl = strlen(p);
//申请内存
dp = (bool**)malloc(sizeof(bool*)*(sl+1));
for(i=0;i<=sl;i++)
{
dp[i] = (bool*)malloc(sizeof(bool)*(pl+1));
}
//初始化
dp[0][0] = 1;
for(i=1;i<=sl;i++)
{
dp[i][0] = 0;
}
for(i=1;i<=pl;i++)
{
dp[0][1] = 0;
}
//do it
for(i=0;i<=sl;i++)
{
for(j=1;j<=pl;j++)
{
if(i>0&&((p[j-1]=='.')||(p[j-1]==s[i-1])))
{
dp[i][j] = dp[i-1][j-1];
}
else if(p[j-1]=='*')
{
dp[i][j] = dp[i][j-2]||(i>0&&dp[i-1][j]&&((p[j-2]=='.')||(p[j-2]==s[i-1])));
}
else dp[i][j] = 0;
}
}
ret = dp[sl][pl];
//释放内存
for(i=0;i<=sl;i++)
{
free(dp[i]);
}
free(dp);
return ret;
}
别人家写的动规
bool isMatch(char* s, char* p) {
int lenS = strlen(s);
int lenT = strlen(p);
bool **table = malloc(sizeof(bool*) * (lenS+1));
for (int i = 0; i <= lenS; i++) {
table[i] = malloc(sizeof(bool) * (lenT+1));
for (int j = 0; j <= lenT; j++) {
table[i][j] = false;
}
}
table[0][0] = true;
for (int j = 1; j <= lenT; j ++) { // only if p[j-1] == * &&
table[0][j] = (j> 1 &&p[j-1] == '*' && table[0][j-2]);
}
for (int i = 1; i <= lenS; i++) {
for (int j = 1; j <= lenT; j++) {
if (p[j-1] != '*') {
table[i][j] = table[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
} else {
table[i][j] = table[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] =='.') && table[i-1][j]);
}
}
}
return table[lenS][lenT];
}
递归C
bool match_sub(char *s, char *p) {
for (;*p && *(p + 1) != '*'; ++s, ++p) {
if (!*s || (*p != *s && *p != '.'))
return false;
}
if (!*p)
return *s == 0;
if (*s && (*s == *p || *p == '.'))
return match_sub(s + 1, p) || match_sub(s, p + 2);
else
return match_sub(s, p + 2);
}
bool isMatch(char* s, char* p) {
int len_p = strlen(p);
int i;
for (i = len_p - 1; i > 1; --i) {
if (p[i - 1] == '*' && p[i + 1] == '*' && p[i] == p[i - 2]) {
memmove(p + i, p + i + 2, strlen(p + i + 2) + 1);
}
}
return match_sub(s, p);
}
非递归非动规（直接撸）
bool isMatch(char* s, char* p) {
char c;
int len = strlen(s);
char *before = NULL;
char *after = NULL;
if(strlen(p) == 0 && len == 0)return true;
while(*p != '\0')
{
if(*(p+1) != '*') //判断 p+1 不为 *
{
if(*p != *s) //p s 相等都++ 不相等判定 p
{
if(after == s && (*p == c || *p == '.') && before < after)
{
p++;
before++;
continue;
}
if(*p != '.') //p 不为 ‘.’ false
return false;
else
{
if(*s == '\0') //p 为‘.’ 判断s 为'\0' false
{
if(*(p-1) == '*' && *(p+1) == '\0' && len != 0)
return true;
return false;
}
}
}
s++;p++;
}else
{ //p+1 为'*'
if(*p != '.') //p 不为'.'
{
if(isMatch(s,p+2))return true;
if(*p != *s) //p s不相等 p+2 s不变
{
p += 2;
}else
{ //*p *s相等
c = *p;
p += 2;
before = s;
while(*s == c)
{
s++;
if(*p == c)
{
p++;
before++;
}
}
after = s;
if(*p == '*')
{
p++;
before--;
}
}
}else
{
p += 2;
while(*p == '.')
{
p++;
if(*p == '*')
{
p++;
continue;
}
if(*s == '\0')return false;
s++;
}
while(*s != *p)
{
if(*(p+1) == '*')break;
if(*s == '\0')
{
if(*p == '\0')break;
else return isMatch(s,p);
}
s++;
}
while(!(isMatch(s,p)))
{
s++;
while(*s != *p)
{
if(*s == '\0')return isMatch(s,p);
if(*(p+1) == '*')break;
s++;
}
}
return true;
}
}
}
if(*s != '\0')return false;
return true;
}
总结：
化整为零。
结语
坚持不懈。
