LintCode 154. Regular Expression Matching

http://www.lintcode.com/en/problem/regular-expression-matching/



A classic Google Problem.

A classic matching dp.

the Dynamic Programming Elements:

1. state
dp i, j means first i of A matching with first j of B.

2. Init
dp i, 0 -> i == 0;
dp 0, j -> isEmpty(j)

3. Func
dp i, j =
if(B.chatAt(j) == '*') {
  check if the Ai matches, then |= helper(i - 1, j)
  and always we can do without Bj, so |= helper(i, j - 2)
} else {
  Bj match Ai? then |= helper(i - 1, j - 1);
  else false;
}

4. Answer
dp m, n

PS: dp size m + 1 by n + 1.

	public class Solution {
	public boolean isMatch(String A, String B) {
	// filter abnormal cases
	if (A == null) {
	return B == null;
	}
	if (A.equals(B)) {
	return true;
	}
	int m = A.length();
	int n = B.length();
	flag = new boolean[m + 1][n + 1];
	dp = new boolean[m + 1][n + 1];
	if (MyLogger.isDebugging) {
	System.out.println("m = " + m + "; n = " + n);
	}
	boolean answer = helper(m, n, A, B);
	if (MyLogger.isDebugging) {
	System.out.println("flag = ");
	for (int i = 0; i <= m; i++) {
	System.out.println(Arrays.toString(flag[i]));
	}
	System.out.println("dp = ");
	for (int i = 0; i <= m; i++) {
	System.out.println(Arrays.toString(dp[i]));
	}
	}
	return answer;
	}
	boolean[][] flag;
	boolean[][] dp;
	boolean helper(int i, int j, String A, String B) {
	if (flag[i][j]) {
	return dp[i][j];
	}
	flag[i][j] = true;
	if (j == 0) {
	dp[i][j] = i == 0;
	return dp[i][j];
	}
	if (i == 0) {
	dp[i][j] = isEmpty(j - 1, B);
	return dp[i][j];
	}
	if (B.charAt(j - 1) == '*') {
	if (j == 1) {
	dp[i][j] = helper(i, j - 1, A, B);
	} else {
	dp[i][j] |= helper(i, j - 2, A, B);
	if (B.charAt(j - 2) == '.' || B.charAt(j - 2) == A.charAt(i - 1)) {
	dp[i][j] |= helper(i - 1, j, A, B);
	}
	}
	} else {
	dp[i][j] = (B.charAt(j - 1) == '.' || B.charAt(j - 1) == A.charAt(i - 1)) && helper(i - 1, j - 1, A, B);
	}
	return dp[i][j];
	}
	boolean isEmpty(int j, String B) {
	if (j % 2 == 0) {
	return false;
	}
	for (int i = 1; i <= j; i += 2) {
	if (B.charAt(i) != '*') {
	return false;
	}
	}
	return true;
	}
	private static class MyLogger {
	static boolean isDebugging = false;
	static boolean isInfoing = true;
	static void debug(Object message) {
	if (isDebugging) {
	System.out.println("MyLogger.Debugging = " + message);
	}
	}
	static void info(Object message) {
	if (isInfoing) {
	System.out.println("MyLogger.Debugging = " + message);
	}
	}
	}
	}

view raw LintCode 154. Regular Expression Matching - LintCode.java hosted with ❤ by GitHub