package leetcode;

/**
 * https://leetcode.com/problems/wildcard-matching/
 */
public class Problem44 {
    public boolean isMatch(String s, String p) {
        return isMatch(s, p, 0, 0);
    }

    private static boolean isMatch(String s, String p, int i, int j) {
        if (i == s.length() && j == p.length()) {
            return true;
        } else if (i == s.length()) {
            return false;
        } else if (j == p.length()) {
            return false;
        }
        boolean match = false;
        if (p.charAt(j) == '*') {
            match |= isMatch(s, p, i + 1, j);
            match |= isMatch(s, p, i, j + 1);
            match |= isMatch(s, p, i + 1, j + 1);
        } else if (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)) {
            match = isMatch(s, p, i + 1, j + 1);
        }
        return match;
    }

    public static void main(String[] args) {
        Problem44 prob = new Problem44();
//        System.out.println(prob.isMatch("aa", "a")); // false
//        System.out.println(prob.isMatch("aa", "*")); // true
//        System.out.println(prob.isMatch("cb", "?a")); // false
//        System.out.println(prob.isMatch("adceb", "*a*b")); // true
//        System.out.println(prob.isMatch("acdcb", "a*c?b")); // false
//        System.out.println(prob.isMatch("acdcb", "a*c?b")); // false
//        System.out.println(prob.isMatch("aabc", "a*?c")); // true
        System.out.println(prob.isMatch("abc", "*abc*")); // true
//        System.out.println(prob.isMatch("abc", "*")); // true
//        System.out.println(prob.isMatch("a", "***")); // true
//        System.out.println(prob.isMatch("abc", "abcd")); // false
    }
}

@@ -142,24 +142,96 @@
 String p) %7B%0A
+        Boolean%5B%5D%5B%5D memo = new Boolean%5Bs.length() + 1%5D%5Bp.length() + 1%5D;%0A
         retu
@@ -251,16 +251,22 @@
  p, 0, 0
+, memo
 );%0A    %7D
@@ -334,16 +334,34 @@
 i, int j
+, Boolean%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -461,32 +461,138 @@
 = s.length()) %7B%0A
+            if (p.charAt(j) == '*') %7B%0A                return isMatch(s, p, i, j + 1, memo);%0A            %7D%0A
             retu
@@ -667,32 +667,107 @@
 alse;%0A        %7D%0A
+        if (memo%5Bi%5D%5Bj%5D != null) %7B%0A            return memo%5Bi%5D%5Bj%5D;%0A        %7D%0A
         boolean 
@@ -858,16 +858,22 @@
 i + 1, j
+, memo
 );%0A     
@@ -906,24 +906,30 @@
  p, i, j + 1
+, memo
 );%0A         
@@ -958,32 +958,38 @@
  p, i + 1, j + 1
+, memo
 );%0A        %7D els
@@ -1096,869 +1096,76 @@
  + 1
-);%0A        %7D%0A        return match;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem44 prob = new Problem44();%0A//        System.out.println(prob.isMatch(%22aa%22, %22a%22)); // false%0A//        System.out.println(prob.isMatch(%22aa%22, %22*%22)); // true%0A//        System.out.println(prob.isMatch(%22cb%22, %22?a%22)); // false%0A//        System.out.println(prob.isMatch(%22adceb%22, %22*a*b%22)); // true%0A//        System.out.println(prob.isMatch(%22acdcb%22, %22a*c?b%22)); // false%0A//        System.out.println(prob.isMatch(%22acdcb%22, %22a*c?b%22)); // false%0A//        System.out.println(prob.isMatch(%22aabc%22, %22a*?c%22)); // true%0A        System.out.println(prob.isMatch(%22abc%22, %22*abc*%22)); // true%0A//        System.out.println(prob.isMatch(%22abc%22, %22*%22)); // true%0A//        System.out.println(prob.isMatch(%22a%22, %22***%22)); // true%0A//        System.out.println(prob.isMatch(%22abc%22, %22abcd%22)); // false
+, memo);%0A        %7D%0A        memo%5Bi%5D%5Bj%5D = match;%0A        return match;
 %0A   

Solve problem 44