P173 通配符匹配

描述#

这个题目说的是，给你一个字符串 s，和一个模式串 p。你要实现一个能支持 ? 和 * 的通配符匹配。其中，? 可以匹配任意单个非空字符，* 可以匹配 0 个字符或任意多个字符。

s 可以是空字符串，也可以是只包含小写字母的非空字符串；p 可以是空字符串，也可以是只包含小写字母、? 或 * 的非空字符串。

注意，p 一定是合法的模式串，并且只有 p 匹配 s 的整个字符串时，才返回 true。

比如说，
s: aa
p: a
模式串 p 不包含通配符，且 s 和 p 不相同，于是这一组 p 和 s 不匹配。
再比如说，
s: ac
p: *

可以匹配任意多个字符，因此这一组 p 和 s 匹配，返回 true。

如果这一组的 s 不变，仍然为 ac，但是把 p 改成 *d：
s: ac
p: *d
由于 p 中的字符 d 无法在 s 中找到匹配字符，因此这一组 p 和 s 不匹配，返回 false。
最后再举个例子：
s: abcde
p: ad?
我们只需要让第一个 * 匹配空字符，第二个 * 匹配 bc，最后的 ? 匹配字符 e，就可以把模式串变成 abcde。于是对于这一组字符串，p 可以匹配 s。

相关视频：简易正则表达式匹配

代码#

public class AlgoCasts {

  private boolean isEqual(char sc, char pc) {
    return sc == pc || pc == '?';
  }

  // Time: O(m*n), Space: O(m*n)
  public boolean isMatchDP(String s, String p) {
    if (s == null || p == null) return false;
    int m = s.length(), n = p.length();
    boolean[][] d = new boolean[m+1][n+1];
    d[0][0] = true;
    for (int i = 1; i <= m; ++i)
      d[i][0] = false;
    for (int j = 1; j <= n; ++j) {
      if (p.charAt(j-1) == '*') d[0][j] = d[0][j-1];
      else d[0][j] = false;
    }

    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        char sc = s.charAt(i-1), pc = p.charAt(j-1);
        if (isEqual(sc, pc)) d[i][j] = d[i-1][j-1];
        else if (pc == '*') d[i][j] = d[i][j-1] || d[i-1][j];
        else d[i][j] = false;
      }
    }
    return d[m][n];
  }

  // Time: O(m*n), Space: O(1)
  public boolean isMatchGreedy(String s, String p) {
    if (s == null || p == null) return false;
    int m = s.length(), n = p.length();
    int i = 0, j = 0, sBegin = -1, pBegin = -1;
    while (i < m) {
      if (j < n && isEqual(s.charAt(i), p.charAt(j))) {
        ++i; ++j;
      } else if (j < n && p.charAt(j) == '*') {
        ++j;
        sBegin = i;
        pBegin = j;
      } else if (pBegin != -1) {
        ++sBegin;
        i = sBegin;
        j = pBegin;
      } else return false;
    }
    while (j < n && p.charAt(j) == '*') ++j;
    return j == n;
  }

}