010. Regular Expression Matching

题目

10. Regular Expression Matching

---

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

递归法

递归讨论，存在两种情况

1. p的第二个不是 * ，那就正常处理
2. p的第二个是 *
   那么两种情况下可以继续

• 如果p的第一个元素和s的当前元素相同
• p的第一个元素是 .

  while (i < s_len && (i < 0 || p[0] == '.' || p[0] == s[i])) {
      if (isMatch(s.substr(i + 1, s_len - i - 1), p.substr(2, p_len - 2))) return true;
      ++i;
  }

其实这块仔细考虑一下，只要出现了 .* 这个组合，肯定是True。

代码为：

class Solution1 {//递归法
public:
	bool isMatch(string s, string p) {

		int s_len = s.length();
		int p_len = p.length();
		if (p_len == 0) return s_len == 0;
		if (p_len == 1 || p[1] != '*') {//p第二个不是*
			if (s_len < 1 || (s[0] != p[0] && p[0] != '.')) return false;
			return isMatch(s.substr(1, s_len - 1), p.substr(1, p_len - 1));
		}
		else {//p第二个是*
			int i = -1;
			while (i < s_len && (i < 0 || p[0] == '.' || p[0] == s[i])) {
				if (isMatch(s.substr(i + 1, s_len - i - 1), p.substr(2, p_len - 2))) return true;
				++i;
			}
			return false;
		}
	}
};

动态规划

• 规划转移方程

We define the state dp[i][j] to be true if s[0..i) matches p[0..j) and false otherwise.

Then the state equations are:

1、dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2、dp[i][j] = dp[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
dp[i][j] 与 dp[i][j - 2] 结果相同，将p[j-1] (‘‘) 直接跳过
3、dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if `p[j - 1] == ‘‘and the pattern repeats for at least1` times.
s[i-1] == p[j-2] 这个时候 p[j-1] == ‘*’ ，即相当于匹配了一次.

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];
	}
};