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()) ||
            (i == s.length() && j + 2 == p.length() && p.charAt(j + 1) == '*')) {
            return true;
        }
        if (j >= p.length()) {
            return false;
        }
        boolean match = false;
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            if (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
                match |= isMatch(s, p, i + 1, j);
            }
            match |= isMatch(s, p, i, j + 2);
        } else {
            if (i < s.length() && 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
        System.out.println(prob.isMatch("abb", "a.*b")); // true
        System.out.println(prob.isMatch("abb", "a.*")); // true
        System.out.println(prob.isMatch("aaa", "ab*a")); // false
        System.out.println(prob.isMatch("", "c*c*")); // true
    }
}

@@ -1033,996 +1033,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem10 prob = new Problem10();%0A        System.out.println(prob.isMatch(%22aa%22, %22a%22)); // false%0A        System.out.println(prob.isMatch(%22aa%22, %22aa%22)); // true%0A        System.out.println(prob.isMatch(%22aaa%22, %22aa%22)); // false%0A        System.out.println(prob.isMatch(%22aa%22, %22a*%22)); // true%0A        System.out.println(prob.isMatch(%22caab%22, %22c.a.%22)); // true%0A        System.out.println(prob.isMatch(%22aab%22, %22c*a*b%22)); // true%0A        System.out.println(prob.isMatch(%22caab%22, %22c*a*b%22)); // true%0A        System.out.println(prob.isMatch(%22aa%22, %22.*%22)); // true%0A        System.out.println(prob.isMatch(%22ab%22, %22.*%22)); // true%0A        System.out.println(prob.isMatch(%22abb%22, %22a.*b%22)); // true%0A        System.out.println(prob.isMatch(%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    %7D
 %0A%7D%0A

Update problem 10