[LeetCode] 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

Thought process:
Recursively check if s and p's substrings match until base case:

1. Base case:
1. p is empty. Return if s is empty.
2. p's length is 1. Return if s's length is also 1 and they match.
3. p's second character is *. Check if s can match p's substring starting from the third character.
1. If so, wildcard character appears 0 times and the strings match. 
2. If not, check if the first character of p and s match. If so, recursively match s's substring starting from its second character.
2. Recurrence:
1. Recursively matches p and s's first characters.

Solution 1 (backtracking):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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

There is another solution using DP.

1. Sub-problem: is a sub-string of s a match of a sub-string of p.
2. Function:
1. If s[i] and p[j] are not wildcards:
1. If s[i] == p[j], f[i][j] = f[i - 1][j - 1].
2. Else, f[i][j] = false.
2. If p[j] == '.', f[i][j] = f[i - 1][j - 1].
3. If p[j] == '*':
1. If s[i] == p[j - 1] or p[j - 1] == '.': f[i][j] = f[i][j - 2] or f[i][j - 1] or f[i - 1][j].
2. If s[i] != p[j - 1]: f[i][j] = f[i][j - 2].
3. Initialization: add a row and column before the strings. String is the rows and pattern is the columns. f[0][0] = true. f[i][0] = false. f[0][i] = true if f[0][i] == '*' and f[0][i - 2] = true.
4. Answer: f[s.length][p.length].

Solution 2 (DP):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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

Time complexity:
Say s.length = a and p.length = b. The overall time complexity is O(ab).