Description

Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Submission

For this problem, we firstly only think about the case where there is only ‘a-z’ and ‘.'(dot). That’s a quite simple problem. There is only one special case, we can match the dot with any one of the letters a-z, and this can be easily recursively implemented.

Now with the ‘*’, every time we check a pattern, we have to check the 0th and 1st letters of the pattern. In a recursive manner, a pattern like “a*” or “.*” can either be “”(empty string) or a letter repeating itself as many times as it can. So we can write this as simple as return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p).

Following is my first submission,

class Solution {
    public boolean isMatch(String s, String p) {
        if(s.length() == 0 && p.length() == 0) {
            return true;
        }
        
        if(p.length() > 0 && p.charAt(0) == '.') {
            if(p.length() > 1 && p.charAt(1) == '*') {
                if(s.length() > 0) {
                    return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p);
                }
                return isMatch(s, p.substring(2));
            }
            if(s.length() > 0) {
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        
        if(p.length() > 0 && p.charAt(0) <= 'z' && p.charAt(0) >= 'a') {
            if(p.length() > 1 && p.charAt(1) == '*') {
                if(s.length() > 0 && s.charAt(0) == p.charAt(0))
                    return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p);
                return isMatch(s, p.substring(2));
            } else if (s.length() > 0 && p.charAt(0) == s.charAt(0)) {
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        
        return false;
    }
}

But as we may find, the function isMatch is called many times and obviously, for a function call isMatch(m, n), a same pair of m and n may be called several times during the execution. To reduce that redundancy, we can store the result of each execution result in a hash map {(int s.length(), int p.length()): boolean result}, or in implementation, an array. For the same pair of string and pattern, the remaining length of the string and pattern can uniquely index them and the final space cost will be O(N^2).

With some modifications based on the previous submission, we can write the dynamic programming program as the following. Since we have to know if a result is already calculated and stored, we need 3 states, in addition to true and false. For the primitive boolean, there are only 2 states. To solve this problem, we use an enum type Result, which contains TRUE and FALSE. If an enum Result type variable is only declared without definition, its state is null.

enum Result {
    TRUE, FALSE
}

class Solution {
    Result[][] res;
    
    public boolean isMatch(String s, String p) {
        int longer = s.length() > p.length()? s.length() : p.length();
        res = new Result[longer + 1][longer  +1];
        return isMatchUtil(s, p) == Result.TRUE ? true : false;
    }
    
    public Result isMatchUtil(String s, String p) {
        if(res[s.length()][p.length()] != null) return res[s.length()][p.length()];
        
        if(s.length() == 0 && p.length() == 0) {
            return res[0][0] = Result.TRUE;
        }
        
        if(p.length() > 0 && p.charAt(0) == '.') {
            if(p.length() > 1 && p.charAt(1) == '*') {
                if(s.length() > 0) {
                    return ((res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2))) == Result.TRUE
                        || (res[s.length() - 1][p.length()] = isMatchUtil(s.substring(1), p)) == Result.TRUE) ? Result.TRUE : Result.FALSE;
                }
                return res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2));
            }
            if(s.length() > 0) {
                return res[s.length() - 1][p.length() - 1] = isMatchUtil(s.substring(1), p.substring(1));
            }
        }
        
        if(p.length() > 0 && p.charAt(0) <= 'z' && p.charAt(0) >= 'a') {
            if(p.length() > 1 && p.charAt(1) == '*') {
                if(s.length() > 0 && s.charAt(0) == p.charAt(0))
                    return ((res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2))) == Result.TRUE
                    || (res[s.length() - 1][p.length()] = isMatchUtil(s.substring(1), p)) == Result.TRUE) ? Result.TRUE : Result.FALSE;
                return res[s.length()][p.length() - 2] = isMatchUtil(s, p.substring(2));
            } else if (s.length() > 0 && p.charAt(0) == s.charAt(0)) {
                return res[s.length() - 1][p.length() - 1] = isMatchUtil(s.substring(1), p.substring(1));
            }
        }
        
        return Result.FALSE;
    }
}

Solution

enum Result {
    TRUE, FALSE
}

class Solution {
    Result[][] memo;

    public boolean isMatch(String text, String pattern) {
        memo = new Result[text.length() + 1][pattern.length() + 1];
        return dp(0, 0, text, pattern);
    }

    public boolean dp(int i, int j, String text, String pattern) {
        if (memo[i][j] != null) {
            return memo[i][j] == Result.TRUE;
        }
        boolean ans;
        if (j == pattern.length()){
            ans = i == text.length();
        } else{
            boolean first_match = (i < text.length() &&
                                   (pattern.charAt(j) == text.charAt(i) ||
                                    pattern.charAt(j) == '.'));

            if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                ans = (dp(i, j+2, text, pattern) ||
                       first_match && dp(i+1, j, text, pattern));
            } else {
                ans = first_match && dp(i+1, j+1, text, pattern);
            }
        }
        memo[i][j] = ans ? Result.TRUE : Result.FALSE;
        return ans;
    }
}