LeetCode 10

题目

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

思想

这道题应该是LeetCode题库中Hard题比较简单的一道了，就是一个很常规的DP题。（我居然还去试了一下贪心~）

既然比较简单就不废话了，直接说动态转移方程组了，我们首先定义一些变量方便解释，被匹配串为s，模式串为p。状态转移数组f[i][j]表示利用p的前j个字符匹配s的前i个字符的匹配结果（成功为true，失败为false）。

那么状态转移方程就很简单了：

• s[i] == p[j] || p[j] == '.'，那么f[i][j] = f[i-1][j-1]，也就是既然s串的第i个字符能和p串的第j个字符匹配，那么如果s串的前i-1个字符和p串的前j-1个字符能匹配则s串的前i个和p串的前j个则能匹配，反之不能。
• p[j] == '*'：
  • s[i] != p[j-1] && p[j-1] != '.'，那么f[i][j] = f[i][j-2]，也就是*号前面的那个字符在匹配的过程当中一个都不使用。
  • else，那么f[i][j] = f[i-1][j] || f[i][j-1] || f[i][j-2]，也就是说要么使用'*'号进行匹配(f[i-1][j])，要么只使用'*'号前面的那个字符匹配，不使用'*'匹配(f[i][j-1])，要么'*'号前面的那个字符在匹配的过程当中一个都不使用（f[i][j-2]），只要有一个是true则能够匹配。

既然是DP题，那么边界条件是必须考虑的部分。因为我一开始i是从1到s.length()，j是1到p.length()。首先一来就能想到f[0][0]是true，其他都是false。但是这个边界条件是不够的。比如isMatch("aab", "c*a*b")，f[1][3]应该是从f[0][2]转移过来的，所以需要更多的边界条件，也就是一开始的*是能匹配空字符串的。所以我把i改到了从0开始,并且第二条也添加了i=0，f[i][j] = f[i][j-2]。

代码

public boolean isMatch(String s, String p) {
    boolean[][] f = new boolean[s.length() + 1][p.length() + 1];
    for (int i = 0; i <= s.length(); i++) {
      for (int j = 0; j <= p.length(); j++) {
        f[i][j] = false;
      }
    }
    f[0][0] = true;
    for (int i = 0; i <= s.length(); i++) {
      for (int j = 1; j <= p.length(); j++) {
        if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
          f[i][j] = f[i - 1][j - 1];
        }
        if (p.charAt(j - 1) == '*') {
          if (i == 0 || (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.')) {
            f[i][j] = f[i][j - 2];
          } else {
            f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i][j - 2];
          }
        }
      }
    }
    return f[s.length()][p.length()];
  }