010 Regular Expression Matching[H]

02-11

1 題目描述

Implement regular expression matching with support for . and *.

難度：Hard

2 題目樣例

. 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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true

3 題意分析

題意很簡單，就是實現正則匹配中的.和*，注意模式串要完全匹配。

4 思路分析

1 遞歸

（定義 $s[k:]$ 表示從下標 $k$ 字元開始到結尾的子串，即 $substr(k)$ ）

分情況討論。

對於.，由於其可以跟任何字元匹配，因此跟正常的匹配過程沒有什麼區別，只要 $s[i]$ 和 $p[j]$ 匹配並且 $s[i+1:]$ 和 $p[j+1:]$ 能匹配即可，即遞歸求解。

對於*，由於其可以匹配0個或者多個，我們也分開考慮。假設 $p[j]$ 為某個字元 $c$ ， $p[j+1]$ 是*，那麼如果原串中根本沒有出現 $c$ ，那麼只要 $s[i:]$ 和 $p[j+2:]$ 匹配即可，如果原串中至少出現了一次 $c$ ，那麼我們去掉首次出現就又回到了0個或者多個的問題上，所以我們只要遞歸求解 $s[i+1:]$ 和 $p[j:]$ 是否匹配即可。

同時在遞歸的過程中緩存相關數據，代碼如下（變數名沒取好，懶得改了）

class Solution {public: vector<vector<int>> m; bool Match(string &s,int l, string &p, int r){ if(m[l][r]!=-1) return m[l][r]; bool ans; if(r==p.size()) ans = (l==s.size()); else{ bool match = (l!=s.size() && (s[l] == p[r] || p[r] == .)); if(p.size()>=2+r && p[r+1] == *) ans = Match(s,l, p,r+2) || (match && Match(s,l+1, p,r)); else ans =match && Match(s,l+1,p,r+1); } m[l][r] = ans; return ans; } bool isMatch(string s, string p) { int k = max(s.size(), p.size()); m.resize(k+1); for(auto &it : m) it.assign(k+1,-1); return Match(s,0,p,0); }};

複雜度不在這裡分析，接下來會提到。

2 動態規劃

注意到剛才的遞歸方法中都是尾遞歸，也就是說我們完全可以寫出一個完全等價的迭代版本，其實這正是動態規劃。

假設s和p的長度分別為m和n，定義dp數組的定義為：

$dp[i][j]$ 表示 $s[0:i]$ 和 $p[0:j]$ 是否匹配，最終答案為 $dp[m-1][n-1]$

所以根據剛才遞歸演算法的分析，反向思維我們很容易就可以寫出轉移方程

$dp[i][j]=egin{cases}s[i]==p[j]&&dp[i-1][j-1],p[j]不是*\ dp[i][j-2] ||(s[i]==p[j]&&dp[i-1][j]),p[j]是*end{cases}$

注意遞推方程中的==應該包含 $p[j]$ 為.而 $s[i]$ 為任意字元的情況。

代碼如下（摘自LeetCode），注意他的 $dp[i][j]$ 表示的字元串第一個字元下標是1而不是0。

class Solution {public: bool isMatch(string s, string p) { int m = s.length(), n = p.length(); vector<vector<bool> > dp(m + 1, vector<bool> (n + 1, false)); dp[0][0] = true; for (int i = 0; i <= m; i++) for (int j = 1; j <= n; j++) if (p[j - 1] != *) dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == .); else dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == .) && dp[i - 1][j]); return dp[m][n]; }};

之前已經提到了，這個複雜度和尾遞歸的形式是完全等價的，因此兩個演算法的時間複雜度都是 $O(mn)$ ，空間複雜度為 $O(mn)$ 。

個人覺得遞歸版本更加符合人類思維（函數式編程？），如果沒有遞歸版本做鋪墊想直接想出動態規劃的方法可能有點困難。

5 後記

看到正則難道第一反應不是自動機嗎！！！！

啊啊啊，氣死我了，還是太菜了，寫了兩個小時的自動機還是有問題，有時間一定要學學正則表達式引擎實現然後寫一個自動機AC的版本，感覺可能還是我自動機構造思路有問題。

當然如果你寫了自動機的版本，也歡迎在評論給出。