@@ -0,0 +1,1725 @@
+package problems;%0A%0A/* %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) ? false%0A isMatch(%22aa%22,%22aa%22) ? true%0A isMatch(%22aaa%22,%22aa%22) ? false%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 Assuming only the second string has . and * %0A */%0A%0Apublic class RegularExpressionMatching %7B%0A    public boolean isMatch(String s, String p) %7B%0A        if (s == null %7C%7C p == null)%0A            return false;%0A%0A        if (p.length() == 0)%0A            return s.length() == 0;%0A%0A        return match(s, 0, p, 0);%0A    %7D%0A%0A    boolean match(String s, int a, String p, int b) %7B%0A        int sl = s.length() - a, pl = p.length() - b;%0A        if (pl == 0)%0A            return sl == 0;%0A%0A        if (pl %3E= 2 && p.charAt(b + 1) == '*') %7B // next one is *%0A            for (int i = 0; i %3C= sl; i++) %7B%0A                if (i %3E 0 && s.charAt(a + i - 1) != p.charAt(b) && p.charAt(b) != '.')%0A                    break;%0A%0A                if (match(s, a + i, p, b + 2))%0A                    return true;%0A            %7D%0A        %7D else if (sl %3E 0 && (s.charAt(a) == p.charAt(b) %7C%7C p.charAt(b) == '.'))%0A            return match(s, a + 1, p, b + 1);%0A%0A        return false;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        RegularExpressionMatching rem = new RegularExpressionMatching();%0A%0A        String s = %22aa%22, p = %22a*%22;%0A        System.out.println(s + %22  %22 + p + %22  %22 + rem.isMatch(s, p));%0A    %7D%0A%7D%0A

Add Regular Expression Matching