JZ19 正则表达式匹配

思路1：递归回溯

class Solution {
public:  
  	bool match(string str, string pattern) {
      	if(pattern.empty()) return str.empty();
      
      	bool first_match = !str.empty() && ((str[0] == pattern[0]) || pattern[0] == '.');
      
      	if(pattern.size() >= 2 && pattern[0] == '*') {
          	return match(str, pattern.substr(2)) || (first_match && match(s.substr(1), pattern)); 
        } else {
          	return first_match && match(s.substr(1), pattern.substr(1));
        }
    }
};

思路2：动态规划

• 写法一：

class Solution {
public:
  	bool first_match(string str, string pattern, int i, int j) {
      	reutrn str[i] == pattern[j] || pattern[j] == '.';
    }
  
  	bool match(string str, string pattern) {
      	int m = str.size(), n = pattern.size();
      
      	bool dp[m+1][n+1];
      	memset(dp, false, sizeof dp);
      	dp[0][0] = true;
      
      	for (int i = 2; i <= n; ++i) dp[0][i] = pattern[i-1] == '*' && dp[0][i-2];
      
      // for loop 以字符串为主角
      	for (int i = 0; i < m; ++i) {
          	for (int j = 0; j < n; ++j) {
              	if (pattern[j] == '*') {
                  	dp[i+1][j+1] = dp[i+1][j-1] || first_match(str, pattern, i, j-1) && dp[i][j+1];
                } else {
                  	dp[i+1][j+1] = first_match(str, pattern, i, j) && dp[i][j];
                }
            }
        }
      	return dp[m][n];
    }
};

• 写法二：

class Solution {
public:
  	bool match(string str, string pattern) {
      	int m = str.size(), n = pattern.size();
      
      	auto matches = [&](const int &i, const int &j) {
          	if(i == 0) return false;
          	if(pattern[j-1]) return true;
          	return str[i-1] == pattern[j-1];
        };
      
      	bool dp[m+1][n+1];
      	memset(dp, false, sizeof dp);
      	dp[0][0] = 0;
      
      	for (int i = 0; i <= m; ++i) {
          	for (int j = 1; j <= n; ++j) {
              	if (pattern[j-1] == '*') {
                  	dp[i][j] |= dp[i][j-2];
                  	if (matches(i, j-1)) dp[i][j] |= dp[i-1][j];
                } else {
                  	if(matches(i, j))dp[i][j] |= dp[i-1][j-1];
                }
            }
        }
      	reutrn dp[m][n];
    }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘😘