【算法20】-【正则表达式匹配】
题目：请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
方法一：递归
import java.util.Arrays;
class Solution {
public boolean isMatch(String s, String p) {
// invoke params check
if (s == null || p == null) {
return false;
}
// match core method
char[] s1 = s.toCharArray();
char[] p1 = p.toCharArray();
return matchCore(s1, p1);
}
public boolean matchCore(char[] s, char[] p) {
if (s.length == 0 && p.length == 0) {
return true;
}
if (s.length != 0 && p.length == 0) {
return false;
}
if (p.length >= 2 && p[1] == '*') {
// [] matches a '*'
if (s.length == 0) {
return matchCore(s, Arrays.copyOfRange(p, 2, p.length));
}
if (s[0] == p[0] || (p[0] == '.' && s.length != 0)) {
// move on the next state
return matchCore(Arrays.copyOfRange(s, 1, s.length), Arrays.copyOfRange(p, 2, p.length))
// stay on the current state
|| matchCore(Arrays.copyOfRange(s, 1, s.length), p)
// ignore a '*'
|| matchCore(s, Arrays.copyOfRange(p, 2, p.length));
} else {
// ignore a '*'
return matchCore(s, Arrays.copyOfRange(p, 2, p.length));
}
}
if (s.length == 0) {
return false;
}
if (s[0] == p[0] || (p[0] == '.' && s.length != 0)) {
return matchCore(Arrays.copyOfRange(s, 1, s.length), Arrays.copyOfRange(p, 1, p.length));
}
return false;
}
} 方法二：动态规划
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}