Leetcode–Regular Expression Matching

The Problem:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Notes:

  1. Note that for each pair of “?*” in p, there is a possible match of skipping this pair in p.
  2. Design the branch condition as:
    1. p[1] !=’*’, which means if p[0] not match then can directly return false;
    2. otherwise, need to consider the ‘?*’ skipping cases:
      1. directly skip by going to p[2]
      2. traversing s while s[id] match p[0], and for each match also consider a skip to p[2]

Java Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s.length()==0 &&  p.length()==0)
            return true;
        if( p.length()==0) 
            return false;
        // check if not have a P:"x*" condition, then the first char must match      
        if(p.length()==1 ||  p.charAt(1)!='*'){
            if(s.length() >0 && (p.charAt(0)=='.' || s.charAt(0) == p.charAt(0))){
               return isMatch(s.substring(1),p.substring(1));
            }
            else
                return false;
        }
        else{
        // for condition: P:"x*", need to consider skipping each pair of "x*"
            //directly skip
            if(isMatch(s, p.substring(2)))
                return true;
            //for each match of s[id] and p:x, try a skip 
            int id = 0;
            while(id < s.length()){
                if(s.charAt(id)==p.charAt(0) || p.charAt(0)=='.'){
                    if(isMatch(s.substring(id+1), p.substring(2)))
                        return true;
                }
                else{
                    break;
                }
                id++;       
            }
            return false;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s