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 *. class Solution {public: bool isMatch(string s, string p) { int m = s.length(),n = p.length(); bool dp[m+1][n+1]; dp[0][0] = true; for (int i = 1; i <= m; i++) dp[i][0] = false; for (int j = 1; j <= n; j++) dp[0][j] = j > 1 && '*' == p[j - 1] && dp[0][j - 2]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 2] || ((s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]); } else { dp[i][j] = (p[j - 1] == '.' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1]; } } } return dp[m][n]; }};