10 Regular Expression Matching
1. Question
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 theentireinput string (not partial).
Note:
s
could be empty and contains only lowercase lettersa-z
.p
could be empty and contains only lowercase lettersa-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
2. Implementation
(1) Recursion
思路: 这题要分清况讨论
如果p是空,则查看s是否为空
如果p长度大于1且p[1] == *, 因为这里的*必须匹配前面的字符0次或多次
如果匹配0次的话,就继续递归地比较s和p.substring(2)
2.如果匹配多次,则需要s[0] == p[0] 或者 p[0] == '.', 然后递归地比较s.substring(1)和p
如果上述情况都不成立的话,则在s[0] == p[0] 或者 p[0] == '.'的情况下,递归比较s.substring(1)和p.substring(1)
class Solution {
public boolean isMatch(String s, String p) {
if (p.length() == 0) {
return s.length() == 0;
}
if (p.length() > 1 && p.charAt(1) == '*') {
return isMatch(s, p.substring(2)) || (s.length() != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p));
}
else {
return s.length() != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
}
}
}
(2)DP
思路:
P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
// s要从0开始,因为s的开头可以被*看为空,如果*表示不匹配之前的character
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j > 1 && p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
}
else {
dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
}
}
}
return dp[m][n];
}
}
3. Time & Space Complexity
Recursion: 时间复杂度O(2^n), 因为,假设P全是a*a*a*这样组成,s = aaaaaaaa 而s的每一个字符都有2种可能:与当前的a*匹配,或者与下一个a*匹配(前一个匹配空), 这样假设s有n个字符,则实际上的复杂度是2^n, 空间复杂度O(L), L是s的长度
Last updated
Was this helpful?