Regular Expression Match II

The first one is a LeetCode problem, and can be found here.

This one, is similar, with the only difference that now we need to take into account '+'. Here is the problem statement:

Write a Simple regex parser, where pattern can contain *, + or .
* -> 0 or none
+ -> one or more
. -> Exactly one character
Examples:
Input - Pattern = a*b+c. data= bcOutput - true
Input - Pattern - abc+ data=abcOutput - true
Input - Pattern - ab* data=c
Output - false

I will still use the recursion method as the first one. When the s.charAt(1) = '+', since there is at least one proceeding character needs to be matched, we need to check if s.charAt(0) == p.charAt(0) or p.charAt(0) == '.'. Moreover, if s is an empty string, it definitely means that they don't match, so simply return false. Now if the first character matches, we need to check how many characters are matched by '+'. I use a loop, if any character in s matches p.charAt(2) (e.g., bbbbbc, and b+c), recursively check the substring of s and p.

Update: 2015 - 03 - 18
I notice the code below has a mistake because I didn't understand regex. '+' matches the proceeding character one or more times, that means the format must be bbbbbc matches b+c, but bbbddc doesn't match b+c.

Here is the updated code.

public static boolean isMatch(String s, String p){
  if(s == null)
   return p == null;
  if(p == null)
   return false;
  if(p.length() == 0)
   return s.length() == 0;
  if(s.equals(p))
   return true;
  if(p.length() == 1 || (p.charAt(1) != '*' && p.charAt(1) != '+')){
   if(s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.'))
    return false;
   return isMatch(s.substring(1), p.substring(1));
  }
  if(p.charAt(1) == '+'){
   //must match at least once
   if(s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.'))
    return false;
   char match = s.charAt(0);
   int index = 0;
   while(index < s.length()){
    if(s.charAt(index) != match)
     break;
    index++;
   }
   return isMatch(s.substring(index), p.substring(2));
  }
  int index_s = -1;
  while(index_s < s.length() && (index_s < 0 || s.charAt(index_s) == p.charAt(0) || p.charAt(0) == '.')){
   if(isMatch(s.substring(index_s + 1), p.substring(2)))
    return true;
   index_s++;
  }
  return false;
 }

public static boolean isMatch(String s, String p) {
  if (p == null || s == null)
   return false;
  if (p.length() == 0)
   return s.length() == 0;
  if (p.equals(s))
   return true;
  if (p.length() == 1 || (p.charAt(1) != '*' && p.charAt(1) != '+')) {
   if (s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.'))
    return false;
   return isMatch(s.substring(1), p.substring(1));
  }
  if (p.charAt(1) == '+') {
   if (s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.')) {
    return false;
   }
   for (int i = 1; i <= s.length(); i++) {
    if (i < s.length() && p.length() > 2 && s.charAt(i) != p.charAt(2))
     continue;
    if (isMatch(s.substring(i), p.substring(2)))
     return true;
   }
   return false;
  }
  int index_s = -1;
  while (index_s < s.length() && (index_s < 0 || s.charAt(index_s) == p.charAt(0) || p.charAt(0) == '.')) {
   if (isMatch(s.substring(index_s + 1), p.substring(2)))
    return true;
   index_s++;
  }
  return false;
 }