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:
if (p.length() == 0) return s.length == 0
;s.length()
is also allowed to be 0;- 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)
).
- 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)
ands.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
If p.charAt(j) == s.charAt(i)
:dp[i][j] = dp[i-1][j-1]
;If p.charAt(j) == '.'
:dp[i][j] = dp[i-1][j-1]
;If p.charAt(j) == '\*'
: here are two sub conditions:
if p.charAt(j-1) != s.charAt(i)
1st char in s and p is matcheddp[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 adp[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()];
}