Leetcode — 132. Palindrome Partitioning II (中文)

12 min readJan 12, 2021

問題連結: https://leetcode.com/problems/palindrome-partitioning-ii/

給予一字串 s, 求我們最少需要切割 s 多少次 讓被切出來的子字串都是回文 (若 s本身就是回文, 那就不需切)

範例, input s = "aab"
最小切割次數為 1 
因為我們只要切一刀, 就可以把字串切成"aa"和"b"兩個回文

想法:

這題是131. Palindrome Partitioning的變形題
在問題131中, 我們被要求回傳所有可以把字串s可以切成回文子字串的各種集合
而這題我們只要用backtracking就可以幫我們解決問題

在helper method中, 我們會一直決定要下哪一刀(當我們可以把字串切成兩個回文子字串的時候,將會是我們決定的第一刀),
當我們決定要切在位置k的時候, 我們就拿到我們的第一塊子字串, 我們就會繼續呼叫helper method來當幫我們看下一刀要切在k+1之後的哪一刀來跟我們前面的子字串做各種組合, 直到我們已不能沒有下一刀可以切
e.g., 給予字串= "aacbc"的時候, 第一刀當然是在a跟a之間, 因為第一個a本身就是回文, 我們接下來就會看"acbc"可以怎麼切可以跟我們一開始的"a"來做組合, 也因此得到其中一個答案是 [“a”, ”a”, ”c”, ”b”, ”c”], 然後又繼續看下去說如果切大一點, 也可以得到[“a”, ”a”, ”cbc”], 而這時因為已經無法再切下一刀了, 就會返回到我們當時切的前一刀, 復原我們剛剛切的前一刀, 改切另一刀

以下為解問題131的 8 ms 程式碼, 贏過 67% -

public List<List<String>> partition(String s) {
        List<List<String>> rst = new ArrayList<>();
        helper(rst,new ArrayList<>(), s, 0, s.length()-1);
        return rst;
    }
    public void helper(List<List<String>> rst, List<String> inner,String s, int i,int j){
        if(i>j)
        {
            rst.add(new ArrayList<>(inner));
            return;
        }
        for(int k=i;k<=j;k++)//cut on k
        {
            if(!isPalindrome(s,i,k)) //skip 
                continue;
            inner.add(s.substring(i,k+1)); //decide to cut
            helper(rst,inner,s, k+1,j);
            inner.remove(inner.size()-1); //redo the previous cut
        }
    }
    public boolean isPalindrome(String s,int i,int j){
        if(i==j)
            return true;
        while(i<j)
        {
            if(s.charAt(i++)!=s.charAt(j--))
                return false;
        }
        return true;
    }

然而, 我們現在要解的這個問題並沒有要求我們回傳所有的組合, 我們只要回傳這些組合中, 需要切最少刀的那個次數就好

所以如果我們按照上述邏輯, 稍微修改程式碼就可以如下 —

public int minCut(String s) {
        return helper(s,0,s.length()-1,0);
    }
    public int helper(String s,int i,int j,int cuts){
        if(isPalindrome(s,i,j))
            return cuts;
        int min = s.length();
        for(int k=i;k<=j;k++) //cut on k
        {
            if(isPalindrome(s,i,k))
                min = Math.min(min, helper(s,k+1,j,cuts+1));
        }
        return min;
    }
    public boolean isPalindrome(String s,int i,int j){
        if(i==j)
            return true;
        while(i<j)
        {
            if(s.charAt(i++)!=s.charAt(j--))
                return false;
        }
        return true;
    }

上述的程式碼通過了Leetcode上大部分的test cases, 但當倒數第三個test case, 當字串長度長一點的時候, 就會因為Time Limit Exceeded而失敗
因為我們用backtracking來解決問題, 但backtracking會為了找每個組合, 所以真的是每個可能性都會去跑完, (尤其是還會先從小刀小刀開始切, 對於解決這題根本毫無幫助), 因此時間複雜度會是指數等級的高, 而這題本身的字串長度比前一個問題字串長度長了, 因此時間複雜度更是指數倍的提升

因此我們必須放棄用backtracking來解決這題, 來看我們可以怎麼改善吧!

程式邏輯:

當我們無法用backtracking的時候, 也許我們可以用dynamic programming動態規劃 來幫我們提升程式速度
動態規劃是一個蠻普遍可以解決高時間複雜度的一個選擇, 因為動態規劃可以幫我們記得我們前面解決過的結果們, 因此我們就不需用遞迴的呼叫方法來找答案了

而這題, 我們可以創一個動態規劃的陣列dp, 來儲存從開頭到某位置i時的字串最少需要多少刀才能讓每個部分都是回文
也就是說, dp[2]代表給予字串s前三個字母組成的字串最少需要切幾刀才能讓字串都是回文

⚠️下面我將會用 s[x,y] 來代表給予字串s中, 在位置x跟位置y之間組成的字串. 比如s為“abcde”, 那 s[0,2] 就是指 “abc”

當我們在loop中, 試著找到dp[i]的最佳解的時候, 我們會走訪每個在i之前的所有位置來看我們最少可以切幾刀, 讓所有部分字串都是回文 (因為i 就是我們字串的終點位置)
當我們發現s[k,i]是回文時, 我們就決定在位置k切, 我們會把字串s切成兩塊, s[0, k-1] 跟 s[k,i], 而因為s[0,k-1]不一定是回文, 所以不代表我們只要切一刀就可以讓s[0,i]變成兩個回文了, 但我們知道的是, 我們可以從陣列取dp[k-1]的值, 讓我們知道我們要切幾刀讓s[0,k-1]變成回文字串
因此如果我們打算在k切下一刀, 那dp[i] 可能的次數 就會是 dp[k-1] + 1 (加1就是在k切下的這刀的意思)
而我們就一直從位置0到i之間, 找合乎條件的k, 進而找到dp[i]的最小刀數 🔪

以下為 968ms 的程式碼, 贏過 17% —

public int minCut(String s) {
        int n = s.length();
        //dp[i] stores the minimum cut needed for s [0,i]
        int[] dp = new int[n];
        Arrays.fill(dp,n);
        for(int i=0;i<n;i++)//ending point
        {
            for(int k=0;k<=i;k++) //make a cut
            {
                if(isPalindrome(s,k,i))
                {
                    if(k==0)
                    {
                        dp[i] = 0; //best case
                        break;
                    }
                    dp[i] = Math.min(dp[i],dp[k-1]+1);
                }
            }
        }
        return dp[n-1];
    }
    public boolean isPalindrome(String s,int left,int right){
        while(left<right)
        {
            if(s.charAt(left++)!=s.charAt(right--))
                return false;
        }
        return true;
    }

因為時間複雜度的減少, 我們總算通過所有的test cases了, 但其實我們發現因為我們不停地呼叫isPalindrome(s, left, right), 我們還是浪費了不少時間, 其實檢查遞迴這件事也可以透過一些方法節省呼叫次數
我們可以利用二維陣列來幫助我們先記錄所有從位置i到位置j是否為回文, 而用二維陣列幫我們紀錄的最大好處就是 — 當我們已知某一連續字串“abcda” 已經不是回文了, 我們不用再去浪費時間一個一個檢查“xabcdax” 是否為回文! 因此時間複雜度大幅降低

也就是, 假設二維陣列稱為isValid, 那isValid[i][j]代表的就是 s[i,j]到底是不是回文; 而s[i,j]是不是回文, 我們在簡單判斷位置i和位置j的字母是否相同後, 再判斷s[i+1,j-1]是不是回文就可知道s[i,j] 可不可能是回文

✏️當i和j的位置過近的時候, 我們也不需靠s[i+1,j-1]來判斷是否為回文, 只要他們的字母相同, 我們就可以直接視他們為回文了 (比如說"aa"和"aba"就是回文, 畢竟兩者中間沒有其他字串有需要讓我們擔心他們會造成整個字串不是回文)

因此, 因為長度大的字串都需要依靠長度小的字串們來判斷是不是回文, 因此我們需要先判斷完長度小的字串們, 才能有效的運用二維陣列來幫忙

我們從長度1到長度n來一個一個找isValid[i,j]的答案, i代表起始位置而j代表字串終點位置

以下為13ms 的程式碼贏過57% 的人—

public int minCut(String s) {
        int n = s.length();
        
        boolean[][] isValid = new boolean[n][n];
        for(int len=1;len<=n;len++) //length of string
        {
            for(int i=0;i<=n-len;i++) // left
            {
                int j=i+len-1; //right
                if(s.charAt(i)!=s.charAt(j))
                    continue;
                if(j-i<=2) 
                    isValid[i][j] = true;
                else
                    isValid[i][j] = isValid[i+1][j-1];
            }
        }
        
        int[] dp = new int[n];
        Arrays.fill(dp,n);
        for(int i=0;i<n;i++)
        {
            for(int k=0;k<=i;k++)
            {
                if(isValid[k][i])
                {
                    if(k==0)
                    {
                        dp[i] = 0; //best case
                        break;
                    }
                    dp[i] = Math.min(dp[i],dp[k-1]+1);
                }
            }
        }
        return dp[n-1];
    }