10. Regular Expression Matching

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

link:

https://www.youtube.com/watch?v=l3hda49XcDE

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/RegexMatching.java

Induction rule:

If pattern.charAt(j) == str.charAt(i) || pattern.charAt(j) == '.' T[i][j] = T[i-1][j-1]

If pattern.charAt(j) == '*', T[i][j] =

T[i][j-2] // in this case, a* counts as 0 occurrence
or
T[i-1][j] if str[i] == pattern[j-1] || pattern[j-1] == '.' // in this case, a occurrence one or multiple times

or false otherwise. (i is text, j is pattern)

Solution from git

public boolean matchRegex(char[] text, char[] pattern) {
    boolean T[][] = new boolean[text.length + 1][pattern.length + 1];

    T[0][0] = true;
    //Deals with patterns like a* or a*b* or a*b*c*
    for (int i = 1; i < T[0].length; i++) {
        if (pattern[i-1] == '*') {
            T[0][i] = T[0][i - 2];
        }
    }

    for (int i = 1; i < T.length; i++) {
        for (int j = 1; j < T[0].length; j++) {
            if (pattern[j - 1] == '.' || pattern[j - 1] == text[i - 1]) {
                T[i][j] = T[i-1][j-1];
            } else if (pattern[j - 1] == '*')  {
                T[i][j] = T[i][j - 2];
                if (pattern[j-2] == '.' || pattern[j - 2] == text[i - 1]) {
                    T[i][j] = T[i][j] | T[i - 1][j];
                }
            } else {
                T[i][j] = false;
            }
        }
    }
    return T[text.length][pattern.length];
}