分类:algorithm| 发布时间:2016-06-30 16:43:00
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
示例 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 = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
'.' 的匹配比较简单,关键在于 '' 的匹配,出现 '' 时表示它前置的字符可出现任意次。 使用递归可较为直观易懂地解决此问题。
class Solution {
public:
bool isMatch(string str, string pat) {
const char *s = str.c_str();
const char *p = pat.c_str();
char prece;
while (*s) {
if (*(p + 1) == '*') {
prece = *p;
++p;
}
if (*p == '*') {
++p;
while (*s) {
if (isMatch(s, p)) {
return true;
}
if (*s != prece && prece != '.') {
return false;
}
++s;
}
} else if (*s == *p || *p == '.') {
++s;
++p;
if (!*p) {
return !*s;
}
} else {
return false;
}
}
while (*p) {
if (*(p + 1) == '*') {
p += 2;
} else {
break;
}
}
return !*p;
}
};
当遇到 '*' 时,对比 s 和 p 是否匹配,否则判断 s 是否等于 prece,或者 prece 是否为 '.'。 若相等则对比 s + 1 和 p。
效率有点低,稍等修改下实现:
class Solution {
public:
bool isMatch(string s, string p) {
return isMatch(s.c_str(), p.c_str());
}
bool isMatch(const char *s, const char *p) {
char prece;
while (*s) {
if (*(p + 1) == '*') {
prece = *p;
++p;
}
if (*p == '*') {
++p;
while (*s) {
if (isMatch(s, p)) {
return true;
}
if (*s != prece && prece != '.') {
return false;
}
++s;
}
} else if (*s == *p || *p == '.') {
++s;
++p;
if (!*p) {
return !*s;
}
} else {
return false;
}
}
while (*p) {
if (*(p + 1) == '*') {
p += 2;
} else {
break;
}
}
return !*p;
}
};
class Solution {
public:
bool isMatch(string s, string p) {
int sSize = s.size(), pSize = p.size(), i, j;
bool checked[sSize+1][pSize+1];
checked[0][0] = true;
if (pSize >= 1) {
checked[0][1] = false;
}
for(j=2; j<=pSize; ++j) {
checked[0][j] = p[j-1] == '*' ? checked[0][j-2] : false;
}
for(i = 1; i <= sSize; ++i) {
for (j = 1, checked[i][0] = false; j <= pSize; ++j) {
if(p[j-1]=='*') {
checked[i][j] = (j>1) && (checked[i][j-2]
|| ((checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')));
} else {
checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
}
}
return checked[sSize][pSize];
}
};
用一个 checked 的二维数组记录 s 和 p 的匹配情况。 扫描 p 时分为两种情况(注意在 checked 中的下标表示字符串的长度):