Regular Expression Matching

[Question]

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

[Analysis]
This problem can be solved in a similar way with Edit Distance. According to its rules, there are four kinds of patterns in this regular expression matching:

"." - Matches any single character.
"c*" - Matches zero or more of character 'c';
".*" - Matches zero or more of any characters;
"c" - Matches a single character 'c';

First, make a match matrix between the word and patterns: e.g. pattern is ".*bc*." and the word is "abbcc"

     .*   b   c*   .
a    0   1   1    0
b    0   0   1    0
b    0   0   1    0
c    0   1   0    0
c    0   1   0    0

"0" in (i,j) represents a possible match between the pattern p[j] and character w[i].
"1" in (i,j) represents no match at all between the pattern p[j] and character w[i].

If there is a match between the pattern and word, there is a path from [1,1] to [m, n] (m is the length of the word and n is the number of patterns), which composed of a series of "0" and the following actions:
1) [i,j] -> [i+1,j+1]  -- end the pattern match at [i,j] and move to next pattern match to [i+1, j+1];
2) [i,j] -> [i,j+1]  -- skip the current pattern match at [i,j] and use next pattern (j+1) on character (i);
3) [i,j]->  [i+1, j] -- continue use current pattern at letter (i) and try to apply to (i+1);

2) 3) are operations allowed only for pattern columns "c*" and ".*".
1) is the only operation allowed for pattern columns "c" and ".".

So back to the above example, we found a path (a match) from [1,1] to [5,4] (marked by red color).


     .*   b   c*   .
a    0   1   1    0
b    0   0   1    0
b    0   0   1    0
c    0   1   0    0
c    0   1   0    0 



[Solution]
//-------------
//--- C++ ---
//-------------
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        string s1 (s);
        string p1 (p);
     
        if ( p1.empty()) return s1 == "";
     
        vector<vector<bool>> map (s1.size()+1, vector<bool>(p1.size()+1, false));
     
        map[0][0] = true;
        for (int i=1; i<p1.size()+1; i++) {
            if (p1[i-1] == '*') map[0][i] = map[0][i-2];
        }
     
        for (int i=1; i<s1.size()+1; i++) {
            for (int j=1; j<p1.size()+1; j++) {
                if (p1[j-1] == '.') {
                    map[i][j] = map[i-1][j-1];
                }
                else if (p1[j-1] == '*') {
                    map[i][j] = map[i][j-2]     //'*' is counted as zero
                            || map[i][j-1]      //'*' is counted as 1
                            || p1[j-2] == '.' && map[i-1][j]  //'.*'
                            || s1[i-1] == p1[j-2] && map[i-1][j];
                }
                else
                    map[i][j] = (s1[i-1] == p1[j-1])? map[i-1][j-1] : false;
            }
        }
        return map.back().back();
    }
};

//---------------
//--- JAVA ---
//---------------
import java.util.*;

public class Solution {
    public static boolean isMatch(String s, String p) {

        List<String> pat = new ArrayList<String> ();
        char[] ap = p.toCharArray();
     
        if (s.length() == 0) return (p.length()==0 || p.equals(".*"));
     
        if (ap.length<=1) {
            if (ap.length==0 && s.length() ==1) return true;
            if (ap.length==0 && ap[0]=='.' && s.length() == 1) return true;
            return false;
        }
     
        // -- parse and generate patterns sub-strings.
        int i = 0;
        while(i<ap.length-1) {
            char a = ap[i];
            char b = ap[i+1];
            if (a == '.') {
                if (b=='*') {
                    pat.add(new String("") + a+b);
                    i++;
                } else {
                    pat.add(new String("") +a);
                }
            }
            else if (a != '*') {
                if (b=='*') {
                    pat.add(new String("") + a +b);
                    i++;
                } else {
                    pat.add(new String("") +a);
                }
            } else { // a=='*'
                return false;
            }
            i++;
        }
        if (i<ap.length) {
        pat.add(new String("") + ap[i]);
        }
     
        // -- generate the matrix.
        int[][] matrix;
        int rows = s.length();
        int cols = pat.size();      
        matrix = new int[rows][cols];

        for (i=0; i<rows; i++) {
            for (int j=0; j<cols; j++) {
                char cs = s.charAt(i);
                matrix[i][j] = 1;
                if (pat.get(j).length() == 2){
                    if ( pat.get(j).equals(".*") ){
                        matrix[i][j] = 0;
                    }
                    else { //"c*"
                        if (pat.get(j).charAt(0) == cs) {
                            matrix[i][j] = 0;
                        }
                    }
                }
                else {
                    if (pat.get(j).equals(".") || pat.get(j).charAt(0) == cs) {
                        matrix[i][j] = 0;
                    }
                }
                System.out.println(matrix[i][j]);
            }
            System.out.println("");
        }
     
       // -- to find a path/match.
        if (matrix[rows-1][cols-1] != 0) return false;
     
        return validateMatch(matrix, 0, 0, pat);
    }
 
    public static boolean validateMatch(int[][] m, int i, int j, List<String> pat) {
        int rows = m.length;
        int cols = m[0].length;
     
        if (i== rows-1 && j==cols-1) return true;

        boolean ret = false;
        if (pat.get(j).length()==2) {
            if (j+1<cols && m[i][j+1] == 0) {
                ret = ret || validateMatch(m, i, j+1, pat);
            }
            if (i+1<rows && m[i+1][j] ==0) {
                ret = ret || validateMatch(m, i+1, j, pat);
            }
        }
     
        if (j+1<cols && i+1<rows && m[i+1][j+1] ==0) {
                ret = ret || validateMatch(m, i+1, j+1, pat);
        }
     
        return ret;  
    }
 
public static void main(String args[])
{
String s = "aasdfasdfasdfasdfas";
String p =  "aasdf.*asdf.*asdf.*asdf.*s";

boolean a = Solution.isMatch(s, p);
System.out.println("a:" + a);
}
}