Regular Expression Matching

LeetCode Q 10 - Regular Expression Matching

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 precedeng 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

Solution

Solution 1: Recursion

Some tips:

1. if (p.length() == 0) return s.length == 0;
2. s.length() is also allowed to be 0;
3. Line 7: if (p.length() >= 2 && p.charAt(1) == '\*'), we can return

• isMatch(s, p.substring(2)); we ignore the 1st char of p, and also the 2nd char of p (i.e. ‘*‘) ;
• or firstMatch && isMatch(s.substring(1), p); when the 1st char in s and p are matched, whether the 1st char in p is the same as that in s or the 1st char in p is ‘.’, since the 2nd char in p is ‘*‘, we can still use then entire p to match s from the 2nd char (i.e. s.substring(1)).

4. Line 9: else, we can return

• firstMatch && isMatch(s.substring(1), p.substring(1)), in this case, the 1st char in s and p must be matched, and we compare their substrings (i.e. s.substring(1) and s.substring(1)).

public boolean isMatch(String s, String p) {
	if (p == null || p.length() == 0) return s.length == 0;
	
	// s could be empty
	boolean firstMatch = (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));

	if (p.length() >= 2 && p.charAt(1) == '*') 
		return isMatch(s, p.substring(2)) || firstMatch && isMatch(s.substring(1), p);
	else
		return firstMatch && isMatch(s.substring(1), p.substring(1));
}

Solution 2: DP

1. If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2. If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3. If p.charAt(j) == '\*': here are two sub conditions:

• if p.charAt(j-1) != s.charAt(i) 1st char in s and p is matched
  • dp[i][j] = dp[i][j-2] in this case, a* only counts as empty
• if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.'
  • dp[i][j] = dp[i-1][j] in this case, a* counts as multiple a
  • dp[i][j] = dp[i][j-1] in this case, a* counts as single a **
  • dp[i][j] = dp[i][j-2] in this case, a* counts as empty

public boolean isMatch(String s, String p) {
	if (p.length() == 0) return s.length() == 0;
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
		dp[0][0] = true;
		for (int i = 0; i < p.length(); i++) {
			if (p.charAt(i) == '\*' && dp[0][i-1]) {
				dp[0][i+1] = true;
			}
		}
	for (int i = 0; i < s.length(); i++) {
		for (int j = 0; j < p.length(); j++) {
			if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') 
				dp[i + 1][j + 1] = dp[i][j];
			if (p.charAt(j) == '\*') {
				if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') 
					dp[i+1][j+1] = dp[i+1][j-1];
				else 
					dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
			}
		}
	}
	return dp[s.length()][p.length()];   
}