https://leetcode.windliang.cc/ 第一時(shí)間發(fā)布

題目描述（困難難度）

image

一個(gè)簡(jiǎn)單規(guī)則的匹配，「點(diǎn).」代表任意字符，「星號(hào)*」 代表前一個(gè)字符重復(fù) 0 次或任意次。

解法一 遞歸

假如沒(méi)有通配符 * ，這道題的難度就會(huì)少了很多，我們只需要一個(gè)字符，一個(gè)字符匹配就行。如果對(duì)遞歸不是很了解，強(qiáng)烈建議看下這篇文章，可以理清一下遞歸的思路。

• 我們假設(shè)存在這么個(gè)函數(shù) isMatch，它將告訴我們 text 和 pattern 是否匹配

  boolean isMatch ( String text, String pattern ) ;

• 遞歸規(guī)模減小

  text 和 pattern 匹配，等價(jià)于 text 和 patten 的第一個(gè)字符匹配并且剩下的字符也匹配，而判斷剩下的字符是否匹配，我們就可以調(diào)用 isMatch 函數(shù)。也就是

  (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.')&&isMatch(text.substring(1), pattern.substring(1));
  

• 遞歸出口

  隨著規(guī)模的減小， 當(dāng) pattern 為空時(shí)，如果 text 也為空，就返回 True，不然的話就返回 False 。

  if (pattern.isEmpty()) return text.isEmpty();
  

綜上，我們的代碼是

public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
    
        //判斷 text 是否為空，防止越界，如果 text 為空， 表達(dá)式直接判為 false, text.charAt(0)就不會(huì)執(zhí)行了
        boolean first_match = (!text.isEmpty() &&
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
        return first_match && isMatch(text.substring(1), pattern.substring(1));
    }

當(dāng)我們考慮了 * 呢，對(duì)于遞歸規(guī)模的減小，會(huì)增加對(duì)于 * 的判斷，直接看代碼吧。

public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
         
        boolean first_match = (!text.isEmpty() &&
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
        //只有長(zhǎng)度大于 2 的時(shí)候，才考慮 *
        if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
            //兩種情況
            //pattern 直接跳過(guò)兩個(gè)字符。表示 * 前邊的字符出現(xiàn) 0 次
            //pattern 不變，例如 text = aa ，pattern = a*，第一個(gè) a 匹配，然后 text 的第二個(gè) a 接著和 pattern 的第一個(gè) a 進(jìn)行匹配。表示 * 用前一個(gè)字符替代。
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));
        } else {
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }

時(shí)間復(fù)雜度：有點(diǎn)兒小復(fù)雜，待更。

空間復(fù)雜度：有點(diǎn)兒小復(fù)雜，待更。

解法二 動(dòng)態(tài)規(guī)劃

上邊的遞歸，為了方便理解，簡(jiǎn)化下思路。

為了判斷 text [ 0，len ] 的情況，需要知道 text [ 1，len ]

為了判斷 text [ 1，len ] 的情況，需要知道 text [ 2，len ]

為了判斷 text [ 2，len ] 的情況，需要知道 text [ 3，len ]

...

為了判斷 text [ len - 1，len ] 的情況，需要知道 text [ len，len ]

text [ len，len ] 肯定好求

求出 text [ len，len ] 的情況，就知道了 text [ len - 1，len ]

求出 text [ len - 1，len ] 的情況，就知道了 text [ len - 2，len ]

...

求出 text [ 2，len ] 的情況，就知道了 text [1，len ]

求出 text [ l1，len ] 的情況，就知道了 text [ 0，len ]

從而知道了 text [ 0，len ] 的情況，求得問(wèn)題的解。

上邊就是先壓棧，然后出棧，其實(shí)我們可以直接倒過(guò)來(lái)求，可以省略壓棧的過(guò)程。

我們先求 text [ len，len ] 的情況

利用 text [ len，len ] 的情況 ，再求 text [ len - 1，len ] 的情況

...

利用 text [ 2，len ] 的情況 ，再求 text [ 1，len ] 的情況

利用 text [1，len ] 的情況 ，再求 text [ 0，len ] 的情況

從而求出問(wèn)題的解

我們用 表示 text 從 i 開(kāi)始到最后，pattern 從 j 開(kāi)始到最后，此時(shí) text 和 pattern 是否匹配。

image

就是圖中橙色的部分.

public boolean isMatch(String text, String pattern) {
    // 多一維的空間，因?yàn)榍?dp[len - 1][j] 的時(shí)候需要知道 dp[len][j] 的情況，
    // 多一維的話，就可以把 對(duì) dp[len - 1][j] 也寫(xiě)進(jìn)循環(huán)了
    boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
    // dp[len][len] 代表兩個(gè)空串是否匹配了，"" 和 "" ，當(dāng)然是 true 了。
    dp[text.length()][pattern.length()] = true;

    // 從 len 開(kāi)始減少
    for (int i = text.length(); i >= 0; i--) {
        for (int j = pattern.length(); j >= 0; j--) {
            // dp[text.length()][pattern.length()] 已經(jīng)進(jìn)行了初始化
            if(i==text.length()&&j==pattern.length()) continue;
            
            boolean first_match = (i < text.length() && j < pattern.length()
                                   && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
            if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
            } else {
                dp[i][j] = first_match && dp[i + 1][j + 1];
            }
        }
    }
    return dp[0][0];
}

時(shí)間復(fù)雜度：假設(shè) text 的長(zhǎng)度是 T，pattern 的長(zhǎng)度是 P ，空間復(fù)雜度就是 O（TP）。

空間復(fù)雜度：申請(qǐng)了 dp 空間，所以是 O（TP），因?yàn)槊看窝h(huán)我們只需要知道 i 和 i + 1 時(shí)候的情況，所以我們可以向 第 5 題 一樣進(jìn)行優(yōu)化。

    public boolean isMatch(String text, String pattern) {
        // 多一維的空間，因?yàn)榍?dp[len - 1][j] 的時(shí)候需要知道 dp[len][j] 的情況，
        // 多一維的話，就可以把 對(duì) dp[len - 1][j] 也寫(xiě)進(jìn)循環(huán)了
        boolean[][] dp = new boolean[2][pattern.length() + 1]; 
        dp[text.length()%2][pattern.length()] = true;

        // 從 len 開(kāi)始減少
        for (int i = text.length(); i >= 0; i--) {
            for (int j = pattern.length(); j >= 0; j--) {
                if(i==text.length()&&j==pattern.length()) continue;
                boolean first_match = (i < text.length() && j < pattern.length()
                        && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                    dp[i%2][j] = dp[i%2][j + 2] || first_match && dp[(i + 1)%2][j];
                } else {
                    dp[i%2][j] = first_match && dp[(i + 1)%2][j + 1];
                }
            }
        }
        return dp[0][0];
    }

時(shí)間復(fù)雜度：不變， O（TP）。

空間復(fù)雜度：主要用了兩個(gè)數(shù)組進(jìn)行輪換，O（P）。

總

這道題對(duì)于遞歸的解法，感覺(jué)難在怎么去求時(shí)間復(fù)雜度，現(xiàn)在還沒(méi)有什么思路，以后再來(lái)補(bǔ)充吧。整體來(lái)說(shuō)，只要理清思路，兩種算法還是比較好理解的。