RegularExpressionMatching.java

package backtracking;

/**
 * Created by gouthamvidyapradhan on 05/12/2017.
 *
 * 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

 Solution: When a wildcard is encountered try to match all the possible prefixes including none, otherwise
 do a simple one to one match. If the end of string is reached simultaneously in both string and pattern
 then return true
 */
public class RegularExpressionMatching {

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        System.out.println(new RegularExpressionMatching().isMatch("aa", "a*a*a"));
    }

    public boolean isMatch(String s, String p) {
        return backTrack(0, 0, s, p);
    }

    private boolean backTrack(int si, int pi, String s, String p){
        if(si >= s.length() && pi >= p.length()) return true; //end of the string has been reached hence return true
        else {
            if(pi >= p.length()) return false; //pattern has exhausted hence return false
            else if(si >= s.length()){
                if(pi + 1 < p.length() && p.charAt(pi + 1) == '*'){
                    return backTrack(si, pi + 2, s, p);
                } else return false; //string has exhausted and pattern does not contain wildcard hence return false
            }
            else if(s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.'){
                if(pi + 1 < p.length() && p.charAt(pi + 1) == '*'){
                    //match 0 or more repeated preceding element
                    if(backTrack(si, pi + 2, s, p)) return true;
                    for(int i = si, l = s.length(); i < l; i ++){
                        if(s.charAt(i) == p.charAt(pi) || p.charAt(pi) == '.'){
                            if(backTrack(i + 1, pi + 2, s, p)) return true;
                        } else {
                            return false;
                        }
                    }
                    return backTrack(s.length(), pi, s, p);
                } else{
                    return backTrack(si + 1, pi + 1, s, p); //not wildcard match immediate chars
                }
            } else{
                if(pi + 1 < p.length() && p.charAt(pi + 1) == '*'){
                    return backTrack(si, pi + 2, s, p);
                } else return false;
            }
        }
    }

}