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) == '?' || s.charAt(i) == p.charAt(j)) {
            match = isMatch(s, p, i + 1, j + 1);
        } else 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);
        }
        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
    }
}

@@ -536,40 +536,10 @@
 == '
-?' %7C%7C s.charAt(i) == p.charAt(j)
+*'
 ) %7B%0A
@@ -556,16 +556,17 @@
   match 
+%7C
 = isMatc
@@ -573,36 +573,32 @@
 h(s, p, i + 1, j
- + 1
 );%0A        %7D els
@@ -596,40 +596,45 @@
     
-%7D else if (p.charAt(j) == '*') %7B
+    match %7C= isMatch(s, p, i, j + 1);
 %0A   
@@ -665,32 +665,36 @@
 h(s, p, i + 1, j
+ + 1
 );%0A            m
@@ -692,45 +692,70 @@
     
-    match %7C= isMatch(s, p, i, j + 1);
+%7D else if (p.charAt(j) == '?' %7C%7C s.charAt(i) == p.charAt(j)) %7B
 %0A   
@@ -761,33 +761,32 @@
           match 
-%7C
 = isMatch(s, p, 
@@ -1459,20 +1459,216 @@
 )); // 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%0A
     %7D%0A%7D%0A

Update problem 44