152. 简易正则表达式匹配

leetcode 10 lintcode 154 字符串 动态规划 免费 讨论

温馨提示:如果题目对您来说比较简单,可以采用 1.5 倍速观看。 立即注册观看更多视频

描述

这个题目说的是,给你一个字符串 s,和一个模式串 p。你要实现一个能支持 .* 的简易正则表达式匹配。

其中,. 可以匹配任意单个非空字符。* 可以将它前面的一个字符重复 0 次或多次。s 可以是空字符串,也可以是只包含小写字母的非空字符串;p 可以是空字符串,也可以是只包含小写字母、.* 的非空字符串。

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

比如说,

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];
  }

}

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。