154 · 正则表达式匹配

链接：LintCode 炼码 - 更高效的学习体验！

题解：

class Solution {
public:/*** @param s: A string * @param p: A string includes "." and "*"* @return: A boolean*/bool isMatch(string &s, string &p) {// write your code hereint m = s.size();int n = p.size();if (m <= 0 && n <= 0) {return true;}std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, false));for (int i = 0; i <= m; ++i) {for (int j = 0; j <= n; ++j) {if (i == 0 && j == 0) {dp[i][j] = true;} else if (j == 0) {} else if (i > 0 && p[j-1] == '.') {// 当前.匹配上字符dp[i][j] |= dp[i-1][j-1];} else if (p[j-1] == '*') {// *表示匹配0前面字符情况，s[i-1] 和p[j-3]前面匹配决定dp[i][j] |= dp[i][j-2];// 把s[i-1] 和 p[j-2] 判断是否匹配，当作一个整体if (i > 0 && j > 1 && (p[j-2] == s[i-1] || p[j-2] == '.')) {dp[i][j] |= dp[i-1][j];}} else if (s[i-1] == p[j-1]) {// 如果字符相等dp[i][j] |= dp[i-1][j-1];}}}return dp[m][n];}
};

class Solution {
public:/*** @param s: A string * @param p: A string includes "." and "*"* @return: A boolean*/std::vector<std::vector<int>> _dp;bool isMatch(string &s, string &p) {// write your code hereint m = s.size();int n = p.size();if (m <= 0 && n <= 0) {return true;}if (n <= 0) {return false;}_dp.resize(m, std::vector<int>(n, -1));return dfs(s, p, 0, 0);}
private:bool dfs(string &s, string &p, int s1, int p1) {if (s1 >= s.size()) {if (p1 >= p.size()) {return true;}if (p[p1] == '*' && p1 + 1 >= p.size()) {return true;}if (p1 + 1 < p.size() && p[p1+1] == '*') {if (dfs(s, p, s1, p1+2)) {return true;}}return false;}if (_dp[s1][p1] != -1) {return _dp[s1][p1] == 1 ? true : false;}if (s[s1] == p[p1]) {if(dfs(s, p, s1+1, p1+1)) {_dp[s1][p1] = 1;return true;}if (p1 + 1 < p.size() && p[p1+1] == '*') {return dfs(s, p, s1+1, p1+2) || dfs(s, p, s1, p1+2);}} else if (p[p1] == '.') {if(dfs(s, p, s1+1, p1+1)) {return true;}if (p1 + 1 < p.size() && p[p1+1] == '*') {cout << "test" << endl;_dp[s1][p1] = (dfs(s, p, s1+1, p1) || dfs(s, p, s1+1, p1+2) || dfs(s, p, s1, p1+2)) == true ? 1 : 0;return _dp[s1][p1] == 1 ? true : false;}} else if (p[p1] == '*') {if (dfs(s, p, s1, p1+1)) {return true;}if (p1 > 0 && (s[s1] == p[p1-1] || p[p1-1] == '.')) {cout << "haha" << endl;if (dfs(s, p, s1+1, p1)) {return true;}if (dfs(s, p, s1+1, p1+1)) {return true;}}} else if (p1 + 1 < p.size() && p[p1+1] == '*') {//cout << "okok" << endl;_dp[s1][p1] = dfs(s, p, s1, p1+2) == true ? 1 : 0;return _dp[s1][p1] == 1 ? true : false;}_dp[s1][p1] = 0;return false;}
};

class Solution {public boolean isMatch(String s, String p) {return search(0, 0,s,p, new Boolean[s.length() + 1][p.length() + 1]);}private boolean search(int i, int j, String s, String p, Boolean[][] memo){if(memo[i][j] != null){return memo[i][j];}boolean ans;if(j == p.length()){ans = i == s.length();}else{boolean firstMatch = (i < s.length() &&(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'));if(j + 1 < p.length() && p.charAt(j + 1) == '*'){ans = (search(i,j + 2, s, p, memo) || firstMatch &&search(i + 1,j, s, p, memo));}else{ans = firstMatch && search(i + 1,j + 1, s, p, memo);}}memo[i][j] = ans;return ans;}
}