Regular Expression Matching

 public static boolean isMatch(String s, String p) {
  int sLen = s.length();
  int pLen = p.length();

  int sIdx = 0;
  for (int i = 0; i < pLen; i++) {
   char pc = p.charAt(i);
   if (i < pLen - 1 && p.charAt(i + 1) == '*') {
    if (isMatch(s.substring(sIdx), p.substring(i + 2)))
     return true;
    for (int j = 0; j < sLen - sIdx; j++) {
     if (pc == '.' || pc == s.charAt(sIdx + j)) {
      if (isMatch(s.substring(sIdx + j + 1),
        p.substring(i + 2)))
       return true;
     } else {
      sIdx += j;
      break;
     }
    }
    i++;
   } else {
    if (sIdx >= sLen)
     return false;

    if (pc == '.' || pc == s.charAt(sIdx))
     sIdx++;
    else
     return false;
   }
  }
  return (sIdx == sLen);
 }