描述

比如说，

s: aa
p: a

模式串 p 不包含通配符，且 s 和 p 不相同，于是这一组 p 和 s 不匹配。

再比如说，

s: ac
p: .*

* 可以把 . 重复两次，变成 .. ，而 . 可以匹配任意字符。因此让第一个 . 匹配 a，第二个 . 匹配 c，即可匹配整个 s。于是对于这一组字符串，p 可以匹配 s。

最后再举个例子，

s: aab
p: c*a*b

只需要让第一个 * 重复 0 次 c，第二个 * 重复两次 a，即可把模式串变成 aab。于是对于这一组字符串，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 isMatch(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-2];
      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 == '*') {
          char preChar = p.charAt(j-2);
          if (isEqual(sc, preChar)) d[i][j] = d[i][j-2] || d[i][j-1] || d[i-1][j];
          else d[i][j] = d[i][j-2];
        } else {
          d[i][j] = false;
        }
      }
    }
    return d[m][n];
  }

  // Time: O(m*n), Space: O(m*n)
  public boolean isMatchShort(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 j = 1; j <= n; ++j)
      if (p.charAt(j-1) == '*')
        d[0][j] = d[0][j-2];

    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 == '*') {
          char preChar = p.charAt(j-2);
          if (isEqual(sc, preChar)) d[i][j] = d[i][j-2] || d[i][j-1] || d[i-1][j];
          else d[i][j] = d[i][j-2];
        } else {
          d[i][j] = false;
        }
      }
    }
    return d[m][n];
  }

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

    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)) {
          cur[j] = pre[j-1];
        } else if (pc == '*') {
          char preChar = p.charAt(j-2);
          if (isEqual(sc, preChar)) cur[j] = cur[j-2] || cur[j-1] || pre[j];
          else cur[j] = cur[j-2];
        } else {
          cur[j] = false;
        }
      }
      boolean[] tmp = cur;
      cur = pre;
      pre = tmp;
      Arrays.fill(cur, false);
    }
    return pre[n];
  }

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

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

}