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
Subscribe to see which companies asked this question
这个问题是一个典型的动态规划。我们设置一个数组dp,dp[i][j]在s[0...i) 符合正则表达式p[0..j)的情况下,为true,反之则为false。
以下是状态转移方程:
当 p[j-1]!='*'
dp[i][j]=i>0&&dp[i-1][j-1]&&(s[i-1]==p[j-1]||p[j-1]=='.')
否则
(忽略.*或者x*) (已经匹配了x) (匹配了x)
dp[i][j]=dp[i][j-2]||(i>0&&dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.'))
class Solution { public: bool isMatch(string s, string p) { int m=s.length(); int n=p.length(); vector<vector<bool>>dp(m+1,vector<bool>(n+1,false)); dp[0][0]=true; for(int i=0;i<=m;i++){ for(int j=1;j<=n;j++){ if(p[j-1]!='*'){ dp[i][j]=i>0&&dp[i-1][j-1]&&(s[i-1]==p[j-1]||p[j-1]=='.'); } else{ dp[i][j]=dp[i][j-2]||(i>0&&dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.')); } } } return dp[m][n]; } };