劍指offer(C++)-JZ19：正則表達(dá)式匹配(算法-動態(tài)規(guī)劃)-創(chuàng)新互聯(lián)

作者：翟天保Steven
版權(quán)聲明：著作權(quán)歸作者所有，商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處

成都創(chuàng)新互聯(lián)公司是一家專業(yè)從事成都做網(wǎng)站、網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司。作為專業(yè)網(wǎng)絡(luò)公司,成都創(chuàng)新互聯(lián)公司依托的技術(shù)實力、以及多年的網(wǎng)站運營經(jīng)驗,為您提供專業(yè)的成都網(wǎng)站建設(shè)、全網(wǎng)整合營銷推廣及網(wǎng)站設(shè)計開發(fā)服務(wù)！題目描述：

請實現(xiàn)一個函數(shù)用來匹配包括'.'和'*'的正則表達(dá)式。

1.模式中的字符'.'表示任意一個字符

2.模式中的字符'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）。

在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配

數(shù)據(jù)范圍:

1.str 只包含從?a-z?的小寫字母。

2.pattern 只包含從?a-z?的小寫字母以及字符?.?和?*，無連續(xù)的?'*'。

3. 0≤str.length≤26?
4. 0≤pattern.length≤26

示例1：

輸入：

"aaa","a*a"

返回值：

true

說明：

中間的*可以出現(xiàn)任意次的a，所以可以出現(xiàn)1次a，能匹配上

解題思路：

本題考察算法-動態(tài)規(guī)劃算法的使用。具體思路如下：

1.建立動態(tài)規(guī)劃表，s1行，s2列，表示進(jìn)行到某個位置時的匹配狀態(tài)，默認(rèn)均為false。

2.初始化首位置為true。首列除了（0,0）位置全為false，首行有可能因為*字符而出現(xiàn)true的情況，所以要處理下。

3.先考慮不為*的情況，這類情況比較簡單。當(dāng)出現(xiàn).符號或者字符相同時，當(dāng)前位置匹配成功；若上一層判斷是true，則表示整體匹配成功；若上一層為false，即使當(dāng)前匹配成功，整體也是失敗的。

4.再考慮有*符號的情況，這個要繼續(xù)細(xì)分。A：*前的字符是.或者能與str對應(yīng)位置字符一致。B：不一致。

5.A類情況，此時有兩種可能使得匹配成功。

一是x*這兩個字符等于空，字符x的數(shù)量當(dāng)做0處理，只參考去除這兩個字符后是否匹配成功，如下圖所示。如果dp[i][j-2]是true，則true，是false則false。

二是將x字符重復(fù)匹配，其實上面的情況可以看做是0個b，若str中出現(xiàn)了連續(xù)的b，則連續(xù)匹配，匹配的依據(jù)就是dp[i-1][j]的狀態(tài)，直到連續(xù)字符中斷。如下圖所示。

綜合來看，A類場景的匹配依據(jù)就可以歸納為：dp[i-1][j]和dp[i][j-2]有一個是true，dp[i][j]就可以匹配成功。

6.A類場景搞懂了，B類自然不難理解。因為字符不一致了，所以只能把x*這兩個字符當(dāng)做空，再結(jié)合dp[i][j-2]的匹配狀態(tài)來判斷是否匹配成功。

7.以上就是完整思路，可以自己畫個表，便于理解。

測試代碼：

class Solution {
public:
    // 匹配
    bool match(string str, string pattern) {
        int s1 = str.length();
        int s2 = pattern.length();
        // 建立動態(tài)規(guī)劃表
        // dp[i][j]表示str前i個字符是否與pattern前j個字符匹配
        vector>dp(s1 + 1, vector(s2 + 1, false));
        // 雙空串可匹配
        dp[0][0] = true;
        // 處理當(dāng)str為空時的情況
        for(int j = 2; j<= s2; ++j)
        {
            if(pattern[j - 1] == '*')
            {
                dp[0][j] = dp[0][j - 2];
            }
        }
        // 雙層循環(huán)
        for(int i = 1; i<= s1; ++i)
        {
            for(int j = 1; j<= s2; ++j)
            {
                // 考慮不為*的情況
                // 當(dāng)出現(xiàn).符號或者字符相同時，當(dāng)前位置匹配成功
                // 若上一層判斷是true，則表示整體匹配成功；若上一層為false，即使當(dāng)前匹配成功，整體也是失敗的
                if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]))
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 若出現(xiàn)*符號，則繼續(xù)分情況考慮
                else if(j >= 2 && pattern[j - 1] == '*')
                {
                    // 若*前的字符是.或者能與str字符串的第i-1個字符一致，則進(jìn)入該分支
                    if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1])
                    {
                        // 如果dp[i][j-2]是true，并賦給dp[i][j]，意味著x*這兩個字符等于空，把字符x的數(shù)量當(dāng)做0處理，此時匹配成功
                        // 如果dp[i][j-2]是false，說明前面的匹配鏈?zhǔn)菙嚅_的
                        // 但有一個機會能完成匹配，那就是*前面的字符和str中對應(yīng)位置字符一致
                        // 但還需要dp[i-1][j]是true才行，它是true的條件其實就等同于字符x連續(xù)重復(fù)了多次
                        // 綜上，dp[i-1][j]和dp[i][j-2]有一個是true，dp[i][j]就可以匹配成功
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    }
                    else
                    {
                        // 如果進(jìn)入該分支，那說明*前的字符和str字符串的第i-1個字符不一致
                        // 不一致卻能匹配成功的情況，就只能是x*這兩個字符為空，也就是把字符x的數(shù)量當(dāng)0處理
                        // 而dp[i][j-2]又是true才可以
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[s1][s2];
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前題目：劍指offer(C++)-JZ19：正則表達(dá)式匹配(算法-動態(tài)規(guī)劃)-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://muchs.cn/article0/djgeio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、定制網(wǎng)站、移動網(wǎng)站建設(shè)、手機網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、網(wǎng)站改版

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容