这两个题看这和像。
Wildcard Matching
'*' Matches any sequence of characters (including the empty sequence).
Regular Expression
'*' Matches zero or more of the preceding element.
高手指点一下。
p*****2 发帖数: 21240
2
dp
p*****3 发帖数: 488
3
低手可以不...
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null)
return false;
int ls = s.length();
int lp = p.length();
boolean[][] dp = new boolean[ls+1][lp+1];
dp[0][0] = true;
for (int i = 1; i <= p.length(); i++) {
dp[0][i] = (p.charAt(i-1) == '*' ? dp[0][i-2] : false);
}
for (int i = 1; i <= ls; i++) {
for (int j = 1; j <= lp; j++) {
if (p.charAt(j-1) != '*' || j == 1) {
dp[i][j] = (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j
-1) == '.') && dp[i-1][j-1];
}
else {
int it = i;
while (!dp[i][j] && it >= 1 && (s.charAt(it-1) == p.
charAt(j-2) || '.' == p.charAt(j-2))) {
if (dp[it-1][j-2])
dp[i][j] = true;
it--;
}