package leetcode;

/**
 * https://leetcode.com/problems/regular-expression-matching/
 */
public class Problem10 {
    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;
        }
        if (i >= s.length() || j >= p.length()) {
            return false;
        }
        boolean match = false;
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            if (s.charAt(i) == p.charAt(j)) {
                match |= isMatch(s, p, i + 1, j);
            }
            match |= isMatch(s, p, i + 1, j + 2);
        } else {
            if (s.charAt(i) != p.charAt(j) && p.charAt(j) != '.') {
                return false;
            }
            match |= isMatch(s, p, i + 1, j + 1);
        }
        return match;
    }

    public static void main(String[] args) {
        Problem10 prob = new Problem10();
        System.out.println(prob.isMatch("aa", "a")); // false
        System.out.println(prob.isMatch("aa", "aa")); // true
        System.out.println(prob.isMatch("aaa", "aa")); // false
        System.out.println(prob.isMatch("aa", "a*")); // true
        System.out.println(prob.isMatch("caab", "c.a.")); // true
//        System.out.println(prob.isMatch("aab", "c*a*b")); // true
//        System.out.println(prob.isMatch("caab", "c*a*b")); // true
//        System.out.println(prob.isMatch("aa", ".*")); // true
//        System.out.println(prob.isMatch("ab", ".*")); // true
//        System.out.println(prob.isMatch("abb", "a.*b")); // true
    }
}

@@ -281,16 +281,17 @@
      if 
+(
 (i == s.
@@ -310,32 +310,115 @@
 j == p.length())
+ %7C%7C%0A            (i == s.length() && j + 2 == p.length() && p.charAt(j + 1) == '*'))
  %7B%0A            r
@@ -455,27 +455,8 @@
 if (
-i %3E= s.length() %7C%7C 
 j %3E=
@@ -603,32 +603,51 @@
 %7B%0A            if
+ (i %3C s.length() &&
  (s.charAt(i) ==
@@ -658,16 +658,39 @@
 harAt(j)
+ %7C%7C p.charAt(j) == '.')
 ) %7B%0A    
@@ -781,28 +781,24 @@
 atch(s, p, i
- + 1
 , j + 2);%0A  
@@ -828,16 +828,34 @@
     if (
+i %3C s.length() && 
 s.charAt
@@ -1426,34 +1426,32 @@
 .a.%22)); // true%0A
-//
         System.o
@@ -1492,34 +1492,32 @@
 a*b%22)); // true%0A
-//
         System.o
@@ -1559,34 +1559,32 @@
 a*b%22)); // true%0A
-//
         System.o
@@ -1621,34 +1621,94 @@
 %22.*%22)); // true%0A
-//
+        System.out.println(prob.isMatch(%22ab%22, %22.*%22)); // true%0A
         System.o
@@ -1726,38 +1726,41 @@
 prob.isMatch(%22ab
+b
 %22, %22
+a
 .*
+b
 %22)); // true%0A// 
@@ -1756,18 +1756,16 @@
 // true%0A
-//
         
@@ -1800,32 +1800,224 @@
 tch(%22abb%22, %22a.*b
+%22)); // true%0A        System.out.println(prob.isMatch(%22abb%22, %22a.*%22)); // true%0A        System.out.println(prob.isMatch(%22aaa%22, %22ab*a%22)); // false%0A        System.out.println(prob.isMatch(%22%22, %22c*c*
 %22)); // true%0A   

Update problem 10