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). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true
一定要 仔细看题仔细看题
这题可以通过 动态规划 解决,
首先我们可以 定义个 boolean match[i][j]
代表 待匹配串s中从0...i的子串与原串0...就的子串的匹配结果 true
匹配成功 false
匹配失败。
接下来就是动态规划的流程了。
i == 0 && j == 0
当i=0
和 j=0
的时候 那么 match[i][j] = true
这毫无疑问的 两个空串匹配肯定是 true
i == 0 && j > 2 && p[j-2] == '*'
当
i == 0 && j > 2 && p[j-2] == '*' ;
match[i][j] == match[i][j-2]
这为什么呢 因为直接我说过 .* 或者 a* 可以匹配匹配任意个任意的字符
那么就是说 s=""
跟 p=".*"
或者 p="a*"
是匹配值 为什么 .* 可以匹配空字符
i != 0 && j == 0
当i=0
和 j!=0
的时候 那么 match[i][j] = false
因为待匹配串长度不为0 但是原串长度是0 这是无法匹配上的 所以是false
p[j] != '*"
match[i+1][j+1] = match[i][j] and (s[i] == p[j] or p[j] == '.' )
这种情况最好理解就不多解释。
p[j] == '*"
因为我之前说过 .*
a*
c*
是一体的
那么它们可以匹配0个或者1个或者多个字符
我们一个一个分情况考虑
a、 当前*匹配0个字符
match[i+1][j+1] = match[i+1][j-1]
举栗
s="aaa" p="aaab*" ===> true
b、 当前*匹配1个字符
match[i+1][j+1] = match[i][j-1] && (s[i] == p[j-1] || p[j-1] == '.')
举栗
s="aa" p="a*" ===>true
b、 当前*匹配多个字符
match[i+1][j+1] = match[i][j+1] && (s[i] == p[j-1] || p[j-1] == '.')
举栗
s="aaaa" p="a*" ===>true
下面贴一下我leetocode ac的代码
public static boolean isMatch(String s, String p) {
boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
match[0][0] = true;
for (int i = 1; i < p.length(); i++) {
if (p.charAt(i) == '*') {
match[0][i + 1] = match[0][i - 1];
}
}
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < p.length() + 1; j++) {
if (p.charAt(j - 1) != '*') {
match[i][j] = match[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
} else if (p.charAt(j - 1) == '*') {
// *匹配0个
match[i][j] = (match[i ][j - 2]
// *匹配1个
|| (match[i - 1][j - 2] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'))
// *匹配多个
|| (match[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'))
);
}
}
}
return match[s.length()][p.length()];
}
其实这题也可以用递归写出来 但是时间复杂度是指数级 用dp的时间复杂度是O(n^2), 最后如果写的有什么不足之处欢迎指定。