10. Regular Expression Matching【hard】

解题思路：

动态规划思想解答这道题：

用 dp[i][j] 表示 s 的前 i 个字符组成的字符串和 p 的 前 j 个字符组成的字符串是否匹配。

转移方程：

当 p[j - 1] == '*' 时：因为 * 可以表示匹配零位或者多位，正则匹配这里要做贪心考虑，分三种情况，只要其中一种满足即为true：

• 匹配零位：则 dp[i][j] = dp[i][j - 2]
• 匹配一位：则 dp[i][j] = dp[i - 1][j - 2] && (满足最后一位匹配)
• 匹配多位：则一位一位匹配，dp[i][j] = dp[i - 1][j] && (满足最后一位匹配)

当 p[j - 1] != '*' 时，dp[i][j] 当且仅当 dp[i - 1][j - 1]为true时，并且最后一位匹配成功时，才为true。

初始状态：

显然，当 s 不为空，p 为空的时候dp[i][j] = false；

其次，当 s 为空，p不为空的时候，考虑到 * 可以匹配零位，所以利用状态转移方程判断其是否应该为true。

实现代码：

// 10. Regular Expression Matching
bool isMatch(string s, string p) {
  int n = s.size();
  int m = p.size();
  // initial
  bool dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      dp[i][j] = false;
    }
  }
  // start
  dp[0][0] = true;
  for (int i = 1; i < n + 1; i++) {
    dp[i][0] = false;
  }
  for (int j = 1; j < m + 1; j++) {
    if (j % 2 == 0) {
      dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
    } else {
      dp[0][j] = false;
    }
  }
  // trans
  bool compare;
  for (int i = 1; i < n + 1; i++) {
    for (int j = 1; j < m + 1; j++) {
      if (p[j - 1] != '*') {
        dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
      } else {
        compare = (s[i - 1] == p[j - 2] || p[j - 2] == '.');
        dp[i][j] = dp[i][j - 2] || (dp[i - 1][j - 2] && compare) || (dp[i - 1][j] && compare);
      }
    }
  }
  return dp[n][m];
}

问题描述：

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 theentireinput string (not partial).

Note:

• scould be empty and contains only lowercase lettersa-z
• pcould be empty and contains only lowercase lettersa-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false