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

results matching ""

    No results matching ""