SimpleRegularExpression.java

import java.util.*;

class SimpleRegularExpression {
      public static boolean isAutocontent(String p) {
        int lp = p.length();
        if (lp == 0) return true;
        if (lp % 2 == 1) return false;
        for(int i=1; i<lp; i+=2){
          if (p.charAt(i) != '*') return false;
        }
        return true;
      }
    
    public static boolean isMatch(String s, String p) {
        int ls = s.length(), lp = p.length();
        if (ls == 0 && (lp == 0 || isAutocontent(p))) return true;
        if (ls == 0 || lp == 0) return false;
        char cs = s.charAt(ls-1), cp = p.charAt(lp-1);
        String news, newp;
        if (cs == cp || cp == '.') {
            news = s.substring(0, ls-1);
            newp = p.substring(0, lp-1);
            return isMatch(news, newp);
        } else {
            if (cp == '*') {
                char cp2 = p.charAt(lp-2);
                if (cs == cp2 || cp2 == '.') {
                    news = s.substring(0, ls-1);
                    newp = p.substring(0, lp-2);
                    return isMatch(s, newp) || isMatch(news, newp) || isMatch(news, p);
                } else
                    newp = p.substring(0, lp-2);
                    return isMatch(s, newp);
            } else
                return false;
        }
    }
    
    public static void main(String[] args) {
      boolean b;
      b = isMatch("aa","a");// → false
      System.out.println(b == false);
      b = isMatch("aa","aa");// → true
      System.out.println(b == true);
      b = isMatch("aaa","aa");// → false
      System.out.println(b == false);
      b = isMatch("aa", "a*");// → true
      System.out.println(b == true);
      b = isMatch("aa", ".*");// → true
      System.out.println(b == true);
      b = isMatch("ab", ".*");// → true
      System.out.println(b == true);
      b = isMatch("aab", "c*a*b");// → true
      System.out.println(b == true);
      b = isMatch("ab", ".*c");
      System.out.println(b == false);
      b = isMatch("a", "ab*a");
      System.out.println(b == false);
      b = isMatch("aasdfasdfasdfasdfas", "aasdf.*asdf.*asdf.*asdf.*s");
      System.out.println(b == true);
    }
}