Regular Expression II
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:
int isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → 0
isMatch("aa","aa") → 1
isMatch("aaa","aa") → 0
isMatch("aa", "a*") → 1
isMatch("aa", ".*") → 1
isMatch("ab", ".*") → 1
isMatch("aab", "c*a*b") → 1
Return 0 / 1 ( 0 for false, 1 for true ) for this problem
Solution:
Time: O(mn)
Space: O(mn)
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
public int isMatch(final String A, final String B) {
// state
// dp[i][j] = B[0 - i) can match A[o - j)
// transition
// dp[i][j] = if B[i] == A[j] || B[i] == '.'
// dp[i - 1][j - 1]
// if B[i] == '*'
// dp[i - 2][j] || dp[i][j - 1] && B[i - 1] == A[j] || '.'
// ignore B[i - 1] use B[i - 1]
// init
// dp[0][0] = true
// dp[i][0] = true if B[i] = '*' && dp[i - 2]
// answer
// dp[m][n]
int m = B.length();
int n = A.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 2; i <= m; i ++) {
char r = B.charAt(i - 1);
if (r == '*' && dp[i - 2][0]) {
dp[i][0] = true;
}
}
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
char c = A.charAt(j - 1);
char r = B.charAt(i - 1);
if (c == r || r == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (r == '*') {
dp[i][j] = dp[i - 2][j] || dp[i][j - 1] && i >= 2 && (c == B.charAt(i - 2) || '.' == B.charAt(i - 2));
}
}
}
// for (int i = 0; i <= m; i ++) {
// System.out.println(Arrays.toString(dp[i]));
// }
return dp[m][n] ? 1 : 0;
}
}