10. Regular Expression Matching
給定一個(gè)輸入字符串s，一個(gè)模式p碟婆，實(shí)現(xiàn)支持.和*的正則匹配：
'.' 匹配單個(gè)字符
'*' 匹配零個(gè)或者多個(gè)元素
- Example 1
輸入：s='aa', p='a'
輸出：false
- Example 2
輸入：s='aa',p='a*'
輸出：true
- Example 3
輸入：s='ab',p='.*'
輸出：true
思路
動(dòng)態(tài)規(guī)劃思路吠勘，首先我們定義P[i][j]為true峰尝，如果s[0...i) 和 p[0...j)匹配狐援，否則為false贡必，那么俱恶，分三種情況：
Screen Shot 2018-10-16 at 10.16.08 PM.png
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), 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] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
return dp[m][n];
}
};
