题解 | #正则表达式匹配#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false));
        //两个都为空串自然匹配
        dp[0][0] = true;
        //初始化str为空的情况，字符串下标从1开始
        for (int i = 2; i <= n2; i++) {
            //可以让自己前面个字符重复0次
            if (pattern[i - 1] == '*')
                //与再前一个能够匹配空串有关
                dp[0][i] = dp[0][i - 2];
        }
        //遍历str每个长度
        for (int i = 1; i <= n1; i++) {
            //遍历pattern每个长度
            for (int j = 1; j <= n2; j++) {
                //当前字符不为*，用.去匹配或者字符直接相同
                if (pattern[j - 1] != '*' && (pattern[j - 1] == '.' ||
                                              pattern[j - 1] == str[i - 1])) {
                    dp[i][j] = dp[i - 1][j - 1];
                    //当前的字符为*
                } else if (j >= 2 && pattern[j - 1] == '*') {
                    //若是前一位为.或者前一位可以与这个数字匹配
                    if (pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1])
                        //转移情况
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    else
                        //不匹配, （直接匹配零个）。
                        dp[i][j] = dp[i][j - 2];
                }
            }
        }
        return dp[n1][n2];
    }
};

首先要弄懂题意，”.*“ 这样的pattern可以匹配任意字符串。

例如”.*"如何匹配abcd呢？

设dp(i)(j)表示pattern中的前j个字符能否匹配str的前i个字符。那么问题就转为求dp(4)(2). 由于pattern[1] 为星号，且前一个字符为点号，故可以匹配掉str的最后一个字符. 由于*可以匹配任意多个字符，故指向pattern的指针可以不动，即dp(4)(2) = dp(3)(2). 依次类推，最后得到dp(4)(2) = dp(0)(2).

问题就转化为空串匹配的问题。dp(0)(2) = dp(0)(0) = true;