Regular Expression Match

Implement wildcard pattern matching with support for ‘?’ and ‘*’ for strings A and B.

The matching should cover the entire input string (not partial).

The first argument of input contains a string A.
The second argument of input contains a string B.

Return 0 or 1:
    => 0 : If the patterns do not match.
    => 1 : If the patterns match.

1 <= length(A), length(B) <= 9e4

Input 1:
    A = "aa"
    B = "a"

Output 1:
    0

Input 2:
    A = "aa"
    B = "aa"

Output 2:
    1

Input 3:
    A = "aaa"
    B = "aa"

Output 3:
    0
    
Input 4:
    A = "aa"
    B = "*"

Output 4:
    1

Input 5:
    A = "aa"
    B = "a*"

Output 5:
    1

Input 6:
    A = "ab"
    B = "?*"

Output 6:
    1

Input 7:
    A = "aab"
    B = "c*a*b"

Output 7:
    0

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] = chars from 0 to i in B can match chars 0 to j 
        // transition
        // dp[i][j] = if B[i] == A[j] || B[i] == '?'
        //          =     dp[i - 1][j - 1]
        //          = if B[i] == '*'
        //          =     dp[i - 1][j - 1] || dp[i - 1][j] || dp[i][j - 1]
        //                    treat as A[j]      ignore it    match previous char as well
        // init
        // dp[0][0] = true
        // dp[i][0] = true if B[i] == '*' and dp[i - 1][0] == true
        // 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 = 1; i <= m; i ++) {
            for (int j = 0; j <= n; j ++) {
                char r = B.charAt(i - 1);
                if (j == 0) {
                    if (r == '*') {
                        dp[i][j] = dp[i - 1][j];
                    }
                    continue;
                }
                char c = A.charAt(j - 1);
                if (c == r || r == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (r == '*') {
                    dp[i][j] = dp[i - 1][j - 1] || dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        // for (int i = 0; i <= m; i ++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        return dp[m][n] ? 1 : 0;
    }
}

Space Optimized:

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] = chars from 0 to i in B can match chars 0 to j 
        // transition
        // dp[i][j] = if B[i] == A[j] || B[i] == '?'
        //          =     dp[i - 1][j - 1]
        //          = if B[i] == '*'
        //          =     dp[i - 1][j - 1] || dp[i - 1][j] || dp[i][j - 1]
        //                    treat as A[j]      ignore it    match previous char as well
        // init
        // dp[0][0] = true
        // dp[i][0] = true if B[i] == '*' and dp[i - 1][0] == true
        // answer
        // dp[m][n]
        int m = B.length();
        int n = A.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        boolean pre = true;
        for (int i = 1; i <= m; i ++) {
            if (!(B.charAt(i - 1) == '*' && dp[0])) {
                boolean temp = dp[0];
                dp[0] = false;
                pre = temp;
            }
            for (int j = 1; j <= n; j ++) {
                boolean temp = dp[j];
                char r = B.charAt(i - 1);
                char c = A.charAt(j - 1);
                if (c == r || r == '?') {
                    dp[j] = pre;
                } else if (r == '*') {
                    dp[j] = pre || dp[j] || dp[j - 1];
                } else {
                    dp[j] = false;
                }
                pre = temp;
            }
            // System.out.println(Arrays.toString(dp));
        }
        // for (int i = 0; i <= m; i ++) {
            // System.out.println(Arrays.toString(dp));
        // }
        return dp[n] ? 1 : 0;
    }
}