题目
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
翻译
实现正则表达式中的 . 和 * 匹配
Hints
Related Topics: String, Dynamic Programming, Backtracking
-
第一个方法就是比较暴力的BF：
- 比较字符串 s 和 p 的 从 i 和 j 开始的子串是否匹配，用递归的方法直到串的最后，最后回溯得到结果
- 那么假设现在走到了 s 的 i 位置和 p 的 j 位置：
- p[j+1]不是 '*'，那么判断 s[i] 和 p[j] 是否相同（注意 '.'）不同返回 false，相同继续递归下一层 i+1，j+1
- p[j+1]是 '*'，那么看 s[i] 开始的子串，如果 s[i]，s[i+1] ... s[i+k] 都等于 p[j]，那么它们都可能是合适的匹配，这样递归就要尝试剩下的 (i,j+2)，(i+1,j+2)，(i+k,j+2)
-
另一个方法就是动态规划：
- 通过 dp[len(s)+1][len(p)+1]来存储计算过的结果
- 遍历的话可以以 p 为外循环，也可以以 s 为外循环
if p[j] == s[j]: dp[i][j]=dp[i-1][j-1] if p[j] == '.': dp[i][j]=dp[i-1][j-1] if p[j] == '*': if p[j-1] != s[i]: dp[i][j]=dp[i][j-2] //a*匹配空 if p[j-1] == s[i] or p[j-1] == '.': dp[i][j] = dp[i][j-1] or //a*匹配一个a dp[i][j] = dp[i][j-2] or //a*匹配空 dp[i][j] = dp[i-1][j] //a*匹配两个a
代码
Java
class Solution {
public boolean isMatch(String s, String p) {
if(s.length()==0 && p.length()==0){
return true;
}
if(p.length()==0){
return false;
}
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)=='*' && i>0 && 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(p.charAt(j)=='.')
dp[i+1][j+1] = dp[i][j];
if(p.charAt(j)==s.charAt(i))
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+1][j-1]||dp[i][j+1]);
}
}
}
}
return dp[s.length()][p.length()];
}
}
Python
class Solution(object):
def helper(self, s, p, i, j):
if j == len(p):
return i==len(s)
if j == len(p)-1 or p[j+1]!='*':
if i==len(s) or (s[i]!=p[j] and p[j]!='.'):
return False
else:
return self.helper(s,p,i+1,j+1)
while i<len(s) and (p[j]=='.' or s[i]==p[j]):
if self.helper(s,p,i,j+2):
return True
i += 1
return self.helper(s,p,i,j+2)
def isMatch(self, s, p):
return self.helper(s,p,0,0)