寫在前面

今天刷了這道DP問(wèn)題，想了半天，沒(méi)有思路，結(jié)果看了題解大吃一驚，這道問(wèn)題居然要O(n^4)的時(shí)間復(fù)雜度，天真的我一直以為L(zhǎng)eetCode題最多也就3次方呢。。。前兩天跪了的美團(tuán)一面也遇到了類似的問(wèn)題，自己對(duì)復(fù)雜度估計(jì)很有問(wèn)題。。。當(dāng)時(shí)是求一個(gè)數(shù)組前k個(gè)最小的的數(shù)組成的數(shù)組，簡(jiǎn)單排序就可以了，然后面試官讓我優(yōu)化，我想了半天都一直在往O(n)奔，結(jié)果面試官提示說(shuō)優(yōu)化快排的過(guò)程，在快排的過(guò)程中就可以完成題目的求解，題目在這兒：最小的k個(gè)數(shù)，唉，之前還以為自己還湊活，越刷題發(fā)現(xiàn)自己越菜，甚至很多以前想到過(guò)的思路都想不起來(lái)了，真是太難受了。。。

題目

核心思路

窮舉

其實(shí)根據(jù)我做的不多的題來(lái)感覺(jué)，這類問(wèn)題最重要的還是先考慮清楚怎么通過(guò)枚舉所有狀態(tài)來(lái)解決問(wèn)題，有了這步之后再去優(yōu)化，就會(huì)稍微簡(jiǎn)單一些。根據(jù)題目的意思，擾亂字符串就相當(dāng)于是把字符串分成左子串和右子串，對(duì)應(yīng)于樹(shù)的左子樹(shù)和右子樹(shù)。那么，一個(gè)字符串str1可以轉(zhuǎn)化為他的擾亂字符串str2也就意味著要么str1的左子串和str2的左子串相等(符合擾亂規(guī)則)，同時(shí)右子串也相等(符合擾亂規(guī)則)；要么str1的左子串和str2的右子串相等并且剩余部分也相等(符合擾亂規(guī)則)，而題目中只是說(shuō)遞歸的分割為兩個(gè)非空子串，并沒(méi)有提如何去分割，也就是說(shuō)我們需要遍歷每一種分割方法，然后分別進(jìn)行上述考慮以此來(lái)窮舉所有可能。因?yàn)轭}目就是遞歸分割的字符串，而這道題又可以看作是樹(shù)形結(jié)構(gòu)，所以可以把重復(fù)的步驟交給遞歸。假設(shè)分割點(diǎn)為i的話可以得到如下的遞推公式：

//s1的左子串等于s2的左子串且右子串相等
boolean flag1 = (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i)));
//s1的左子串等于s2的右子串且剩余部分相等
boolean flag2 = (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));

這道題的下標(biāo)計(jì)算真的比較愁人，多拿兩個(gè)例子試一試或許能比較好的找到下標(biāo)的關(guān)系。

圖示

窮舉代碼

class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1 == null || s2 == null)
            return false;
        if(s1.length() == 1){
            return s1.charAt(0) == s2.charAt(0);
        }
        if(s1.length() == 2){
            return (s1.charAt(0) == s2.charAt(0) && s1.charAt(1) == s2.charAt(1)) || (s1.charAt(1) == s2.charAt(0) && s1.charAt(0) == s2.charAt(1));
        }
        boolean ans = false;
        for(int i = 1; i < s1.length() && !ans; i++){
            ans = ans || (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) || (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));
        }
        return ans;
    }
}

有了遞歸的遞推公式，代碼就比較簡(jiǎn)單了，對(duì)于長(zhǎng)度等于2的判斷其實(shí)可加可不加，不加也可以在遞歸里遍歷到，加了能稍微減少一點(diǎn)壓棧彈棧。

窮舉優(yōu)化

(1)備忘錄優(yōu)化

遞歸窮舉時(shí)間復(fù)雜度很高，優(yōu)化是必須的，而遞歸的優(yōu)化就不得不想到備忘錄了，所以我們可以使用一個(gè)備忘錄數(shù)組來(lái)記錄之前計(jì)算過(guò)的結(jié)果。不過(guò)還需要考慮備忘錄用幾維，表示什么，由于考慮的問(wèn)題在遞歸時(shí)與字符串的子串相關(guān)，那么至少需要一個(gè)起始點(diǎn)和一個(gè)結(jié)束點(diǎn)，又因?yàn)樾枰瑫r(shí)記錄s1和s2兩個(gè)字符串的子串，也就是說(shuō)需要四維數(shù)組來(lái)記錄訪問(wèn)過(guò)的值，還是很恐怖的。。。

備忘錄優(yōu)化代碼

根據(jù)上邊的窮舉法把取子串的操作變成每次遞歸傳遞下標(biāo)然后每訪問(wèn)過(guò)一對(duì)串就添加進(jìn)備忘錄即可。

class Solution {
    String s1;
    String s2;

    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        this.s1 = s1;
        this.s2 = s2;
        int len = s1.length();
        int[][][][] memo = new int[len][len][len][len];
        return matches(0, len - 1, 0, len - 1, memo);
    }

    public boolean matches(int i, int j, int m, int n, int[][][][] memo) {
        if (memo[i][j][m][n] != 0) {
            return memo[i][j][m][n] == 1;// 0為未訪問(wèn)，1為可以匹配，2為不匹配
        }
        if (j - i == 0) {
            memo[i][j][m][n] = s1.charAt(i) == s2.charAt(m) ? 1 : 2;
            return memo[i][j][m][n] == 1;
        }
        if (j - i == 1) {
            boolean temp = (s1.charAt(i) == s2.charAt(m) && s1.charAt(j) == s2.charAt(n))
                    || (s1.charAt(j) == s2.charAt(m) && s1.charAt(i) == s2.charAt(n));
            memo[i][j][m][n] = temp ? 1 : 2;
            return memo[i][j][m][n] == 1;
        }

        boolean ans = false;
        for (int len = 1; len < j - i + 1 && !ans; len++) {
            ans = ans || (matches(i, i + len - 1, m, m + len - 1, memo) && matches(i + len, j, m + len, n, memo))
                    || (matches(i, i + len - 1, n - len + 1, n, memo) && matches(i + len, j, m, n - len, memo));
        }
        memo[i][j][m][n] = ans ? 1 : 2;
        return ans;
    }
}

(2)根據(jù)字母出現(xiàn)次數(shù)優(yōu)化

說(shuō)實(shí)話這個(gè)優(yōu)化我是沒(méi)想到，被官方的示例給帶跑了，我以為它提供的測(cè)試用例怎么也得是滿足字母出現(xiàn)次數(shù)相同的情況下才判斷是不是擾亂吧。。。實(shí)際可能確實(shí)是這樣，但是對(duì)于遞歸考慮子串的時(shí)候，還是很有可能會(huì)出現(xiàn)字母出現(xiàn)次數(shù)都不同的情況，所以每層遞歸都優(yōu)先判斷兩個(gè)子串的字母出現(xiàn)次數(shù)是否相同，不同的話就不需要繼續(xù)深層遞歸了。

優(yōu)化代碼

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null)
            return false;
        if (s1.equals(s2))
            return true;
        if (s1.length() == 1) {
            return s1.charAt(0) == s2.charAt(0);
        }
        int[] letters = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            letters[s1.charAt(i) - 'a']++;
            letters[s2.charAt(i) - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (letters[i] != 0)
                return false;
        }

        boolean ans = false;
        for (int i = 1; i < s1.length() && !ans; i++) {
            ans = ans
                    || (isScramble(s1.substring(0, i), s2.substring(0, i))
                            && isScramble(s1.substring(i), s2.substring(i)))
                    || (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
                            && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));
        }
        return ans;
    }
}

這樣優(yōu)化后運(yùn)行時(shí)間可以達(dá)到2ms，極大的進(jìn)行了剪枝，保證了不滿足條件的盡快被篩選掉。

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

或許直到現(xiàn)在我才真的直到什么是動(dòng)態(tài)規(guī)劃，為什么動(dòng)態(tài)規(guī)劃效率高，以前一直模糊的不得了。
遞歸是自頂向下的，它會(huì)先考慮兩個(gè)完整的字符串，然后不斷深入，直到遞歸出口，也就是子串只剩下一個(gè)字符時(shí)，開(kāi)始向上返回結(jié)果，最終得到最后的結(jié)果；而動(dòng)態(tài)規(guī)劃實(shí)際上省略了深入的過(guò)程，自底向上其實(shí)就是直接考慮遞歸出口所要解決的問(wèn)題，也就是一個(gè)字符時(shí)的情況，這也是為什么DP問(wèn)題總要去考慮最小子問(wèn)題的原因，然后根據(jù)最小子問(wèn)題向上一點(diǎn)點(diǎn)得到最終的最優(yōu)解。
另外，DP的作用是提高效率，他是通過(guò)自底向上復(fù)用先前的結(jié)果以此達(dá)到天然剪枝的效果，不過(guò)實(shí)際上他還是會(huì)遍歷所有的可能，這也是為什么上邊的剪枝結(jié)果要比DP更快，上邊的剪枝在字符串還是比較長(zhǎng)的時(shí)候就有可能直接剪掉返回，而DP則不會(huì)，DP還是要從短到長(zhǎng)一點(diǎn)點(diǎn)遍歷每個(gè)可能。

DP思路

最小子問(wèn)題：通過(guò)上邊的思考，兩個(gè)字符串的最小子問(wèn)題就是只有一個(gè)字符的情況，在這種情況下，是不是滿足擾亂的條件就是看這兩個(gè)字符是不是相等即可。
DP數(shù)組的定義：通過(guò)窮舉加備忘錄時(shí)的考慮，我們可以定義一個(gè)四維數(shù)組dp[i][j][m][n]來(lái)表示s1 i 到 j 的子串和s2 m 到 n 的子串是否匹配，不過(guò)一方面滿足擾亂的前提是兩個(gè)字符串長(zhǎng)度相等，所以j - i == n - m的部分才是須要考慮的；另一方面，我們使用DP自底向上是要從最小子問(wèn)題湊出最終結(jié)果，所以這樣枚舉的時(shí)候不方便，換成長(zhǎng)度更合適，字符串的DP問(wèn)題很多都是通過(guò)枚舉長(zhǎng)度來(lái)解決的。dp[len][i][j]表示s1從 i 開(kāi)始長(zhǎng)度是len的子串與s2從 j 開(kāi)始長(zhǎng)度是len的子串是否滿足擾亂關(guān)系。
狀態(tài)轉(zhuǎn)移方程：對(duì)于長(zhǎng)度大于等于2的兩個(gè)子串，通過(guò)遞歸時(shí)的圖示很容易可以想到類似遞歸的轉(zhuǎn)移方程：對(duì)于每個(gè)確定的分割方式，要么s1左子串與s2左子串相等(可以通過(guò)擾亂轉(zhuǎn)化)，同時(shí)另一部分相等(可以通過(guò)擾亂轉(zhuǎn)化)；要么s1左子串與s2右子串相等，同時(shí)剩余部分相等。

boolean temp = false;
for (int k = 1; k < len && !temp; k++) {
    temp = temp || dp[k][i][j] && dp[len - k][i + k][j + k]
          || dp[k][i][j + len - k] && dp[len - k][i + k][j];
}
dp[len][i][j] = temp;

上邊的代碼通過(guò)遍歷每一個(gè)可能的分割點(diǎn)k，然后對(duì)每個(gè)分割點(diǎn)分別獲取dp[k][i][j] && dp[len - k][i + k][j + k]表示上述第一種情況；dp[k][i][j + len - k] && dp[len - k][i + k][j]表示上述第二種情況。這里的下標(biāo)真的不是很好算，挺愁人的。最后，根據(jù)dp數(shù)組的定義，題目求解的答案即是dp[s1.length][0][0]。

DP代碼

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        int length = s1.length();
        boolean[][][] dp = new boolean[length + 1][length][length]; // dp[len][i][j] 表示從i,j開(kāi)始，長(zhǎng)度為len的字符串是否匹配

        for (int len = 1; len <= length; len++) {
            for (int i = 0; i < length - len + 1; i++) {
                for (int j = 0; j < length - len + 1; j++) {
                    if (len == 1) {
                        dp[len][i][j] = s1.charAt(i) == s2.charAt(j);
                    } else {
                        boolean temp = false;
                        for (int k = 1; k < len && !temp; k++) {
                            temp = temp || dp[k][i][j] && dp[len - k][i + k][j + k]
                                    || dp[k][i][j + len - k] && dp[len - k][i + k][j];
                        }
                        dp[len][i][j] = temp;
                    }
                }
            }
        }

        return dp[length][0][0];
    }
}

總結(jié)

DP問(wèn)題真的是一類很難的問(wèn)題，記得前些天看的ycx講的DP問(wèn)題提到，這類問(wèn)題在定義dp數(shù)組的時(shí)候更多時(shí)候是需要靠經(jīng)驗(yàn)的，而且定義的選擇稍有不對(duì)就很可能解決不了問(wèn)題，還是需要慢慢去積累，真的好難。最后，如果想看閆氏DP分析法，請(qǐng)點(diǎn)擊這里，講解的還是很透徹的，不過(guò)DP難是肯定了，需要繼續(xù)努力，進(jìn)步啊，感恩相遇~