程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Leetcode : Regular Expression Matching

Leetcode : Regular Expression Matching

編輯:關於C++

對於leetcode上這個題目,我用了不少時間來消化。
題目大意如下:


實現兩個字符串s,t的匹配,其中t字符串中的
‘.’ 能匹配任何一個字符.
‘*’ 能充當0個或者多個前面一個字符.
匹配結果要覆蓋整個字符串

幾個例子:
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

比如說最後這個例子c*a*b 能夠和aab匹配 就說明第一個* 充當了0個c,第二個 *充當了兩個a。


該題有兩種較為普遍的解法:遞歸和動規。以下我就兩種方法進行簡要的分析。

遞歸法

該題的一個難點就是當t字符串中出現了符號“ * ”時該如何處理,有時候一下子並不能夠清晰的把代碼給寫出來。我們可以直觀地想,出現“ * ”時,該“ * ”可以充當0個,1個,2個…前面的字符,充當的過程還需要滿足條件 (s[i]==p[0]) 或者(p[i]==’.’ && s[i]!=’’)。 我們將每種可能都與s串進行一遍比較,若有一種可以匹配成功,即是匹配成功。

若t字符串中的當前匹配符號不是符號“ * ”就好辦多了,我們直接對 s[i]==p[0] 或者 p[0]==’.’ 進行判斷,若匹配成功,那麼就可以進行下一步匹配。

參考代碼如下:(參考別人)

//遞歸方法
bool isMatch(string s, string p) 
{
        if ( p.empty() ) return s.empty();
        // p[1]不是*
        if ( p[1]!='*' )
        {
            return ( s[0]==p[0] || (p[0]=='.' && !s.empty()) ) && isMatch(s.substr(1), p.substr(1));
        }
        // p[1]是*
        int i = 0;
        for ( ; s[i]==p[0] || (p[0]=='.' && i

動態規劃法

若是對動態規劃較為熟悉的人可能對於該方法可能更順手些。

我們提供一個二維空間集合f[i][j] 其表示字符串s[0..i-1]能否和t[0…j-1]匹配成功,我們很快可以得到動態規劃轉移方程

當t[j-1]!=’*’時 f[i][j] = f[i-1][j-1] && ( s[i-1] == t[j-1] )

這個很好理解,s[i-1]和t[j-1]若相同,那麼其s[0…i-2] 至 t[0…j-2]仍然能匹配成功時,那麼這兩段字符串就是匹配成功。

當t[j-1]==’*’時 t[j-1]可以充當0個或者多個t[j-2],只要滿足以下兩個條件中任何一個,f[i][j] 結果即為true
t[j-1]充當0個t[j-2] : f[i][j] = f[i][j-2] t[j-1]充當1個及以上t[j-2] :f[i][j] = (s[i - 1] == p[j - 2] || ‘.’ == p[j - 2]) && f[i - 1][j]

上述動規方程中的 f[i - 1][j] 包含了 t[j-1]充當2個,3個…多個t[j-2] 的所有可能性,並且動規過程中,我們已經計算並保存了結果。

參考代碼如下:(參考別人)

bool isMatch(string s, string p) {

 int m = s.size(), n = p.size();
        vector> f(m + 1, vector(n + 1, false));

        f[0][0] = true;//空串與空串匹配成功
        for (int i = 1; i <= m; i++)//s串與空串匹配結果為false
            f[i][0] = false;
        // p[0..j - 1] 能與空串匹配 需滿足 p[j - 1]=='*' 並且 p[0..j - 3] 能與空串匹配
        for (int j = 1; j <= n; j++)
            f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p[j - 1] != '*')
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
                else
                    f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];

        return f[m][n];
}

兩種方法不同的思想,其中有相通的部分,都能解決問題,記錄一下以便以後回顧。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved