題目(10)

核心思路

首先感謝一下這位大佬的思路：labuladong
對(duì)于這道題，直接使用正則庫(kù)調(diào)用個(gè)函數(shù)就能AC，不過(guò)這就沒(méi)有意義了，該寫(xiě)還是要自己寫(xiě)的。

不考慮 '*'

通過(guò)對(duì)題目的理解，這道題最大的難點(diǎn)就是在 '*' 這個(gè)符號(hào)上，如果不考慮它，問(wèn)題就會(huì)變的比較簡(jiǎn)單。只需要將 '.' 這個(gè)萬(wàn)能匹配符考慮一下就可以得到如下的代碼：

public boolean isMatch(String s, String p) {
        if (p.isEmpty())
            return s.isEmpty();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != p.charAt(i) && p.charAt(i) == '.')
                return false;
        }
        return true;
    }

這樣很容易實(shí)現(xiàn)，因?yàn)?'.' 和一個(gè)正常的字符沒(méi)有什么區(qū)別，所以只要遍歷一次即可。接下來(lái)我們來(lái)考慮 * 號(hào)。

考慮 '*'

我們可以從*的定義入手，在正則中他是用來(lái)重復(fù)前面的字符 零次或者多次。這也就是說(shuō)，當(dāng)我們遇到一個(gè)字符的后邊是 星號(hào)，那么我們就可以選擇要么一個(gè)都不匹配，要么匹配多個(gè)，但是具體匹配幾個(gè)似乎很難決定，比如看如下的例子：
(1)s = "aaa", p = "a*"; (2)s = "aaa", p = "a*a";
對(duì)于第一個(gè)例子，*與兩個(gè)a相匹配。而對(duì)于第二個(gè)例子，*號(hào)匹配兩個(gè)a將會(huì)返回不匹配，只能匹配一個(gè)。這也就告訴我們實(shí)際上須要匹配幾個(gè)要去嘗試，當(dāng)前匹配個(gè)數(shù)不合適還需要回溯才能確定，因此我們完全可以把這個(gè)過(guò)程丟給遞歸。
首先，我們將上邊不考慮*的方法改寫(xiě)成遞歸：當(dāng)前字符匹配，比較后邊的字符；當(dāng)前字符不匹配，直接返回，遞歸代碼如下：

public boolean isMatch(String s, String p){
       if(p.isEmpty()) return s.isEmpty();
       if(s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')
            return isMatch(s.substring(1), p.substring(1));
        return false;
}

然后把它改成考慮*的情況：當(dāng)前字符匹配且下一個(gè)符號(hào)不是*，可以直接將 s 和 p 的下標(biāo)向后移；不論當(dāng)前字符匹配或不匹配，只要下一個(gè)符號(hào)是*，那么就要考慮是當(dāng)前字符不匹配，還是匹配一個(gè)(匹配一個(gè)將s下標(biāo)前進(jìn)，交給遞歸就可以匹配多個(gè))。所以我們可以按照這個(gè)思路完成下面的代碼：

代碼

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty())
            return s.isEmpty();
        boolean first_match = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');

        if (p.length() >= 2 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p));
        } else {
            return first_match && isMatch(s.substring(1), p.substring(1));
        }
    }
}

這里將首字符匹配保存為一個(gè)變量，就是因?yàn)?code>*號(hào)，他的存在可以使不匹配的字符直接跳過(guò)，因此，主要判斷條件以*為主，有*和沒(méi)有分開(kāi)即可，然后多次使用這個(gè)變量判斷是否移動(dòng)下標(biāo)。

優(yōu)化

上邊的代碼已經(jīng)可以通過(guò)提交，不過(guò)效率并不高，而且我們使用的方法只不過(guò)是遞歸回溯，并沒(méi)有一點(diǎn)涉及到DP思想，那么遞歸怎么優(yōu)化呢？ 常見(jiàn)的方法便是備忘錄，這樣就可以避免重復(fù)訪問(wèn)，從而達(dá)到提高效率的效果。

class Solution {
    int[][] memo;

    public boolean isMatch(String s, String p) {
        if (p.isEmpty())
            return s.isEmpty();
        memo = new int[s.length() + 1][p.length() + 1];// 0表示未訪問(wèn)，1表示true，-1表示false
        memo[s.length()][p.length()] = 1;
        return isMatched(s, p, 0, 0);
    }

    public boolean isMatched(String s, String p, int i, int j) {
        if (memo[i][j] != 0) {
            // 重復(fù)訪問(wèn)，直接訪問(wèn)備忘錄
            return memo[i][j] == 1;
        }

        if (j >= p.length())
            return i >= s.length();

        boolean first_match = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');

        if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
            memo[i][j] = isMatched(s, p, i, j + 2) || (first_match && isMatched(s, p, i + 1, j)) ? 1 : -1;
        } else {
            memo[i][j] = first_match && isMatched(s, p, i + 1, j + 1) ? 1 : -1;
        }
        return memo[i][j] == 1;
    }
}

這里簡(jiǎn)單提一下，對(duì)于這道正則題，加備忘錄的第一感覺(jué)總是不會(huì)出現(xiàn)重復(fù)的訪問(wèn)。因?yàn)楹孟衩總€(gè)字符或者s和p的下標(biāo)都是之前沒(méi)有訪問(wèn)過(guò)的，不會(huì)出現(xiàn)重復(fù)似的，不過(guò)，可以考慮adef 和 a*a*，請(qǐng)讀者畫(huà)圖嘗試一下就可以發(fā)現(xiàn)其中的重復(fù)部分了。
接下來(lái)我們來(lái)看下一道十分相似的題。

題目(44)

核心思路

這道題其實(shí)就是上一道題的改編，不再是真正的正則表達(dá)式，而是將.改變成?，將*號(hào)含義變成匹配任意字符串，功能更加強(qiáng)大了。所以需要重新考慮怎么遞推，由于*變成可以直接匹配任意字符，那么就是說(shuō)它獨(dú)立開(kāi)來(lái)了，和他前邊的字符沒(méi)有關(guān)系了，這樣的話，我們就可以直接根據(jù)當(dāng)前字符是否是*號(hào)來(lái)區(qū)分，是*號(hào)可以選擇直接跳過(guò)，也可以選擇匹配s串中的一個(gè)(或多個(gè))字符，剩下的同樣交給遞歸即可。同時(shí)不要忘了加備忘錄哦。

代碼

class Solution {
    int[][] memo;// 0表示未訪問(wèn)，1表示匹配，2表示不匹配

    public boolean isMatch(String s, String p) {
        memo = new int[s.length() + 1][p.length() + 1];// 比字符串長(zhǎng)度大1防止遞推時(shí)越界
        return dp(s, p, 0, 0);
    }

    public boolean dp(String s, String p, int i, int j) {
        if (memo[i][j] != 0) {
            return memo[i][j] == 1;
        }

        if (j == p.length()) {
            return i == s.length();
        }

        if (p.charAt(j) == '*') {
            boolean flag = false;
            if (i < s.length()) {
                flag = flag || dp(s, p, i + 1, j);
            }
            memo[i][j] = flag || dp(s, p, i, j + 1) ? 1 : 2;
        } else {
            memo[i][j] = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') && dp(s, p, i + 1, j + 1)
                    ? 1
                    : 2;
        }
        return memo[i][j] == 1;
    }

}

整體思路和上邊幾乎一模一樣，只要稍稍考慮一下下一個(gè)要比較的字符是哪幾個(gè)即可，剩下的全部托付給了遞歸。(ps:有人可能會(huì)說(shuō)這就是回溯加備忘錄，不是DP，其實(shí)DP也就是個(gè)名字/一種思想而已，不用那么較真，理解它的思想才是重要的)
另外，在官方題解中給出了另一種回溯解法可以大大優(yōu)化這一道題，如果想要了解請(qǐng)點(diǎn)這里，筆者也是在學(xué)習(xí)理解，如有說(shuō)的不對(duì)的地方還請(qǐng)指出，感恩相遇~