Leetcode 44. Wildcard Matching

https://leetcode.com/problems/wildcard-matching/

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

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

This is a string-matching advance problem. The approach will be simpler to string matching.
Match each char of s and p.

Let’s write a recursive approach,

If char is
1. ‘?’: It could be matched with a single character.
2. ‘*’: It could match with single, double, or multiple characters.

1. Recursion

 /**
     * * Recursion
     * * Time: O(2^n)
     * * Space: O(n): Auxiliary stack space
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        return isMatch(s, s.length() - 1, p, p.length() - 1);
    }

    public boolean isMatch(String s, int i, String p, int j) {
        if (i < 0 && j < 0)
            return true;
        if (i < 0 && j >= 0) {
            for (int k = 0; k <= j; k++) {
                if (p.charAt(k) != '*')
                    return false;
            }
            return true;
        }
        if (j < 0) return false;
        // if char at p is ?, it will match with any single char of s. 
        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')
            return isMatch(s, i - 1, p, j - 1);
        if (p.charAt(j) == '*')
            return isMatch(s, i, p, j - 1) || isMatch(s, i - 1, p, j);
        return false;
    }

Take * as single character 
isMatch(s, i, p, j - 1)

Take * as multiple character
isMatch(s, i - 1, p, j)

2. Memorization :

Step 1: Find out variables in recursion.

In it above recursion
variables are an index i and j

Note: Variables are two then create 2D array, if the variables are a 3 array
created a 3D array.

Step 1: Create temp 2-D array ()with size:
i = 0 to i = s.length()

j = 0 to j = p.length()

int[][] dp = new int[s.length()][p.length()];

 /**
     * * Memorization
     * * Time: O(m * n)
     * * Space: O(n): Auxiliary stack space + O(m * n)
     * 
     * @param s
     * @param p
     * @return
     */
    public boolean isMatchMemorization(String s, String p) {
        // -1 default, 0 false and 1 = true
        int[][] dp = new int[s.length()][p.length()];
        for (int[] col : dp)
            Arrays.fill(col, -1);

        return isMatchMemorization(s, s.length() - 1, p, p.length() - 1, dp);
    }

    public boolean isMatchMemorization(String s, int i, String p, int j, int[][] dp) {
        if (i < 0 && j < 0)
            return true;
        if (i < 0 && j >= 0) {
            for (int k = 0; k <= j; k++) {
                if (p.charAt(k) != '*')
                    return false;
            }
            return true;
        }
        if (j < 0) return false;
        if (dp[i][j] != -1)
            return convert(dp[i][j]);

        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
            boolean result = isMatchMemorization(s, i - 1, p, j - 1, dp);
            dp[i][j] = convert(result);
            return result;
        }

        if (p.charAt(j) == '*') {
            // taking * as zero and more size
            boolean result = isMatchMemorization(s, i, p, j - 1, dp) || isMatchMemorization(s, i - 1, p, j, dp);
            dp[i][j] = convert(result);
            return result;
        }
        return false;
    }

    boolean convert(int data) {
        return data == 0 ? false : true;
    }

    int convert(boolean data) {
        return data ? 1 : 0;
    }

Time Complexity: O(length(s) * length(p)) ~ O(m*n)
Space Complexity: O(n): Auxiliary stack space + O(m * n)

Now it’s time to optimize space complexity.

3. Tabulation

 /**
     * * DP 
     * * Time Complexity: O(m*n)
     * * Space: O(m*n)
     * @param s
     * @param p
     * @return
     */

    public boolean isMatchDP(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;

        for (int i = 1; i < dp[0].length; i++) {
            if (p.charAt(i - 1) == '*')
                dp[0][i] = true;
            else
                break;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                if (p.charAt(j - 1) == '*')
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }

Time Complexity: O(length(s) * length(p)) ~ O(m*n)
Space Complexity: O(length(s)+1 * length(p)+1) ~ O(m*n)

4. Tabulation space optimized

public boolean isMatchDPOptimized(String s, String p) {
        boolean[] prev = new boolean[p.length()+1];
        prev[0] = true;

        for (int i = 1; i < prev.length; i++) {
            if (p.charAt(i - 1) == '*')
                prev[i] = true;
            else
                break;
        }
        boolean[] current = new boolean[p.length()+1];

        for (int i = 1; i < s.length() + 1; i++) {
            current[0] = false;
            for (int j = 1; j < current.length; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
                   current[j] = prev[j - 1];
                else if (p.charAt(j - 1) == '*')
                    current[j] = current[j - 1] || prev[j];
                else
                    current[j] = false;
            }
            boolean[] temp = prev;
            prev = current;
            current = temp;
        }

        return prev[prev.length-1];
    }

Time Complexity: O(length(s) * length(p)) ~ O(m*n)
Space Complexity: O(length(p)+1) ~ O(n)
Assuming length p = n

Happy Learning !!!