Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

解題思路

時間復(fù)雜度： O(nm)
字符串比較一般都可以先想到動態(tài)規(guī)劃，此題只需要計算一個n*m的矩陣即可求解，所以復(fù)雜度是O(nm)。（n和m分別是p和s的長度）
1、n*m的矩陣用于記錄正則式p從開頭到下標(biāo)i結(jié)束的子串與目標(biāo)字符串s從開頭到下標(biāo)i結(jié)束的子串的比較結(jié)果。
2、基于下標(biāo)小的元素以及比對字符可以計算出下標(biāo)大的元素，從而填滿整個矩陣。
3、矩陣計算完畢后，返回對應(yīng)元素即可。
4、矩陣的元素是怎么計算的，用一個例子來說明，如下圖：

圖1. 示例

1. 橫向是目標(biāo)字符串s，縱向是正則式p。定義該矩陣為C
2. 初始化第一行。當(dāng)s和p均為空時，匹配正確，所以C[0][0] = 1。當(dāng)p為空串而s不為空時，一定匹配錯誤，所以第一行其他列均賦值為0。
3. 初始化第一列。第一列表示s為空串，這種情況只有當(dāng)p中出現(xiàn)*時匹配結(jié)果可能為真，如圖中第一列標(biāo)紅的位置。當(dāng)p中出現(xiàn)*時，該元素同一列上前兩個元素任意一個為真，它就為真。具體原因在4.中解釋，所以C[2][0] = C[0][0]。
4. 計算其他元素。有如下情況：

p[i] == p[j] || p[i] == '.': // 該元素對應(yīng)子串匹配正確 
        C[i + 1][j + 1] = C[i][j] 
p[i] == '*': // x*代表字符x出現(xiàn) 0 次、1 次、1次以上。
        C[i + 1][j + 1] = C[i - 1][j + 1] // x*代表x出現(xiàn)0次時，匹配結(jié)果等同于“x*”沒出現(xiàn)過
                                    //即當(dāng)前 p 的子串向前跳兩個字符與當(dāng)前 s 的子串的匹配結(jié)果

        C[i + 1][j + 1] = C[i][j + 1] // x*代表x出現(xiàn)1次時，匹配結(jié)果等同于沒有該星號，
                                      // 以前一個字符為結(jié)尾的 p 的子串與 s 的子串的匹配結(jié)果。

        C[i + 1][j + 1] = C[i + 1][j] // x*代表x出現(xiàn)1次以上時，只要當(dāng)前 s 的子串的結(jié)尾字
                                    // 符與 p 的子串的 * 的前一個字符（別忘了'.'的情況）能匹配上，
                               // 當(dāng)前匹配結(jié)果就等同于以 * 前一位字符結(jié)尾的 p 子串與 s 子串的匹配結(jié)果。

簡單來說，p[i] == '*'的情況只需要考慮如圖中的反向“L”區(qū)域，其他位置出現(xiàn) 1 則當(dāng)前位置為 1 ，否則為 0 。

解題源碼

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> check(n + 1, vector<bool>(m + 1, false));// 用 false 初始化所有元素
        
        // 初始化第一個元素，其他第一行元素已經(jīng)初始化為 false 了
        check[0][0] = true;
        // 初始化第一列
        for (int i = 0; i <n; ++i) {
            if (p[i] == '*') {
                check[i + 1][0] = i >= 1 && check[i - 1][0] || i >= 0 && check[i][0];
            }
        }
        // 計算其他元素
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (p[i] == '.' || p[i] == s[j]) check[i + 1][j + 1] = check[i][j];
                else if (p[i] == '*') {
                    check[i + 1][j + 1] = check[i - 1][j + 1] || check[i][j + 1] || (p[i - 1] == s[j] || p[i - 1] == '.') && check[i + 1][j];
                }
            }
        }
        // 返回結(jié)果
        return check[n][m];
    }
};

參考

Discuss