Leetcode Q10 正则匹配动态规划解法
June 10 2017

这道题首先要把题目读懂,不然会因为想当然而制造了很多错误的解法。在isMatch()这个方法里,要求前者s与p模式匹配,而不是s是p的子集或者相反。另外,关于星号的定义也与真正的正则不太相同。这里的星号”*“是要匹配星号前面的字符,有零个或者多个。因此,根据题目可以假设模式中如果出现星号,则星号之前必然有字符,而不会出现诸如”**“这样的字符。

因此,我们可以稍微改变一下匹配字符p的形状。在没有星号的字符后面认为添加一个不存在的字符(比如”#”号),使得这个匹配字符工整,方便后续操作。

这样的转换下,如下字符则会变成下列的样子,把新生成的字符叫做pp

a -> a#
aa -> a#a#
a*a -> a*a#

因此制作如下两个辅助私有方法:

// 判断当前字符是否是多重匹配
private boolean isMultiple(int i, String pp) {
    return pp.charAt(i + 1) == '*';
}

// 判断当前字符是否是通配符
private boolean isAnySingle(int i, String pp) {
    return pp.charAt(i) == '.';
}

基本思路解法是利用动态规划,创建一个二维数组dp[][]。拿s = "aab"p = "c*a*b"来举例,制作好的二维数组如下所示:

  a a b
c*      
a*      
b#      

只需要把这个表格填满就得到了结果。先填写第一列:

boolean hasSingleBefore = false;
for (int j = 0; j < pp.length() / 2; j++) {
    if (j == 0) {
        if (isAnySingle(j, pp) || pp.charAt(j) == s.charAt(0)) {
            dp[0][j] = true;
        } else {
            dp[0][j] = false;
        }
    } else {
        if (isMultiple(j * 2, pp)) {
            if (dp[0][j - 1]) {
                dp[0][j] = true;
            } else if (hasSingleBefore) {
                dp[0][j] = false;
            } else if (pp.charAt(j * 2) == s.charAt(0) || isAnySingle(j * 2, pp)) {
                dp[0][j] = true;
            } else {
                dp[0][j] = false;
            }
        } else {
            if (hasSingleBefore) {
                dp[0][j] = false;
            } else if (pp.charAt(j * 2) == s.charAt(0) || isAnySingle(j * 2, pp)) {
                dp[0][j] = true;
            } else {
                dp[0][j] = false;
            }
        }
    }
    if (!isMultiple(j * 2, pp)) hasSingleBefore = true;
}

这是一段极为复杂的代码,需要考虑很多情况。前几行首先填写dp[0][0]的值。接下来判断当前匹配字符的情况:

  1. 是多重匹配字符

这种情况下,如果上一个匹配为true的话,那么意味着匹配字符如果新添加任何字符,这里都应该为true。比如”xxx”和”xxx”模式匹配成功,那么匹配字符新添加一多重匹配字符不影响匹配结果,因为新添加的字符可以为零或者多个。

如果上一个是为false的话,说明之前的字符匹配失败,但并不代表当前字符匹配也失败。因为”a”和”b“匹配失败,但是如果匹配字符加上一个”a“则匹配成功。因此这里使用一个hasSingleBefore来记录先前的匹配记录中是否曾存在过单一匹配字符的匹配情况。如果有的话则当前字符匹配继续失败。

如果没有的话还要看原字符和当前匹配字符是否相同,或者匹配字符是否为通配符,如果两者任一为真,则当前匹配也为true,反之则假。

  1. 是单一匹配字符

若当前匹配字符为单一匹配字符的情况(后面接”#”),则检查以前匹配中是否出现过单一匹配,如果出现过则当前为false。为什么呢?拿”a”和”a#”来举例,因为单一匹配曾出现过,所以匹配字符再添加任何单一字符的话,原字符并没有新的字符来应对,因此必然为false

如果没出现过的话,同样检查字符是否相同或者通配符,是为真,反之为假。

结果如下:

  a a b
c* false    
a* true    
b# false    

获取完第一列之后,按顺序填入每一行。每个值根据不同情况会依赖于自己左上方的三个值。这里又分为多种情况来讨论。注意这里循环的外层使用pp.length() / 2来限制,是因为处理后的pp字符串为原来的扩展长度。在使用循环计数器j的时候,需要乘以2,才能转换成pp中的字符。

for (int j = 0; j < pp.length() / 2; j++) {
    for (int i = 1; i < s.length(); i++) {
        if (isMultiple(j * 2, pp)) {
            if (j - 1 >= 0 && dp[i][j - 1]) {
                dp[i][j] = true;
            } else if (dp[i - 1][j]) {
                if (isAnySingle(j * 2, pp) || pp.charAt(j * 2) == s.charAt(i)) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            } else {
                dp[i][j] = false;
            }
        } else {
            if (isAnySingle(j * 2, pp) || pp.charAt(j * 2) == s.charAt(i)) {
                if ((j - 1 >= 0 && dp[i - 1][j - 1])) {
                    dp[i][j] = true;
                } else if (dp[i - 1][j]) {
                    dp[i][j] = false;
                } else {
                    dp[i][j] = false;
                }
            } else {
                dp[i][j] = false;
            }
        }
    }
}
  1. 当前为多重匹配字符

这个值跟DP表格中左上方三个值的真假都相关。如果上方的值为真,那么该值为真。为什么?考虑一个s字符”a”和匹配字符”a*“,如果匹配字符添加任何一个多重匹配值,二者应该继续保持匹配状态,因为多重匹配可以为零。

如果上方的值为假,但是左侧的值为真,则要看当前字符和匹配字符是否相同,或者匹配字符是否为通配符。

  1. 为单一匹配字符

与上面差不多。

其实里面的逻辑有些冗余,代码有待继续整理优化。但是考虑到做了这题已经花了我一整天,能够通过已经很不容易,索性使用这个原本记录我的思考的算法,而不是精简优化。

完整代码(33ms)在此

Currently

Software Engineer at Yahoo!

Previously

Full Stack Engineer at Prosper Marketplace

Previously

Front End Engineer at BillGuard (Acquired by Prosper)