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)) {
                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("aa", ".*")); // true
//        System.out.println(prob.isMatch("ab", ".*")); // 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("abb", "a.*b")); // true
    }
}

@@ -743,32 +743,54 @@
 ) != p.charAt(j)
+ && p.charAt(j) != '.'
 ) %7B%0A            
@@ -1239,34 +1239,32 @@
 %22a*%22)); // true%0A
-//
         System.o
@@ -1292,16 +1292,20 @@
 ch(%22
+c
 aa
+b
 %22, %22
+c.a
 .
-*
 %22));
@@ -1360,16 +1360,20 @@
 ch(%22
+a
 ab%22, %22
-.*
+c*a*b
 %22));
@@ -1373,32 +1373,34 @@
 a*b%22)); // true%0A
+//
         System.o
@@ -1416,32 +1416,33 @@
 n(prob.isMatch(%22
+c
 aab%22, %22c*a*b%22));
@@ -1442,32 +1442,34 @@
 a*b%22)); // true%0A
+//
         System.o
@@ -1489,37 +1489,96 @@
 ob.isMatch(%22
-c
 aa
-b
 %22, %22
-c*a*b
+.*%22)); // true%0A//        System.out.println(prob.isMatch(%22ab%22, %22.*
 %22)); // true

Update problem 19