@@ -0,0 +1,2033 @@
+/***%0A * Implement regular expression matching with support for '.' and '*'.%0A *%0A * '.' Matches any single character.%0A * '*' Matches zero or more of the preceding element.%0A *%0A * The matching should cover the entire input string (not partial).%0A *%0A * The function prototype should be:%0A * bool isMatch(const char *s, const char *p)%0A *%0A * Some examples:%0A * isMatch(%22aa%22,%22a%22) fasle%0A * isMatch(%22aa%22,%22aa%22) true%0A * isMatch(%22aaa%22,%22aa%22) fasle%0A * isMatch(%22aa%22, %22a*%22) true%0A * isMatch(%22aa%22, %22.*%22) true%0A * isMatch(%22ab%22, %22.*%22) true%0A * isMatch(%22aab%22, %22c*a*b%22) true%0A */%0A%0Apublic class Solution %7B%0A    public boolean isMatch(String s, String p) %7B%0A        return isMatch(s, 0, p, 0);%0A    %7D%0A    // Solution 1: O(n) O(1)%0A    /*%0A    private boolean isMatch(String s, int i, String p, int j) %7B%0A        int sl = s.length();%0A        int pl = p.length();%0A        if (j == pl)  return i == sl;%0A        if ((j %3C pl - 1 && p.charAt(i + 1) != '*') %7C%7C j == pl - 1) %7B%0A            return (i %3C sl && s.charAt(i) == p.charAt(j) %7C%7C p.charAt(j) == '.') && isMatch(s, i + 1, p, j + 1);%0A        %7D%0A        while ((i %3C sl && s.charAt(i) == p.charAt(j)) %7C%7C (p.charAt(j) == '.' && i %3C sl)) %7B%0A            if (isMatch(s, i, p, j + 2))%0A                return true;%0A            i++;%0A        %7D%0A        return isMatch(s, i, p, j + 2);%0A    %7D%0A    */%0A%0A    // Solution 2: O(n), O(1)%0A    private boolean isMatch(String s, int i, String p, int j) %7B%0A        int sl = s.length();%0A        int pl = p.length();%0A        if (j == pl)  return i == sl;%0A        // p(j + 1) is not '*'%0A        if ((j %3C pl - 1 && p.charAt(j + 1) != '*') %7C%7C j == pl - 1) %7B%0A            if (i %3C sl && (s.charAt(i) == p.charAt(j) %7C%7C p.charAt(j) == '.')) %0A                return isMatch(s, i + 1, p, j + 1);%0A            else %0A                return false;%0A        %7D%0A        // If it is,%0A        while ((i %3C sl && s.charAt(i) == p.charAt(j)) %7C%7C (p.charAt(j) == '.' && i %3C sl)) %7B%0A            if (isMatch(s, i, p, j + 2))%0A                return true;%0A            i++;%0A        %7D%0A        return isMatch(s, i, p, j + 2);%0A    %7D%0A%0A%7D%0A

add RegularExpressionMatching.java