LeetCode 第 131 号問題：分割回文串

本文首發于公衆号「五分鐘學算法」，是

​​圖解 LeetCode ​​​系列文章之一。

個人網站：

​​​https://www.cxyxiaowu.com​​

題目來源于 LeetCode 上第 131 号問題：分割回文串。題目難度為 Medium，目前通過率為 45.8% 。

題目描述

給定一個字元串 s，将 s

傳回 s

示例:

輸入: "aab"
輸出:
[
  ["aa","b"],
  ["a","a","b"]
]      

題目解析

首先，對于一個字元串的分割，肯定需要将所有分割情況都周遊完畢才能判斷是不是回文數。不能因為 abba

既然需要将所有的分割方法都找出來，那麼肯定需要用到DFS（深度優先搜尋）或者BFS（廣度優先搜尋）。

在分割的過程中對于每一個字元串而言都可以分為兩部分：左邊一個回文串加右邊一個子串，比如 "abc" 可分為 "a" + "bc" 。 然後對"bc"分割仍然是同樣的方法，分為"b"+"c"。

在處理的時候去優先尋找更短的回文串，然後回溯找稍微長一些的回文串分割方法，不斷回溯，分割，直到找到所有的分割方法。

舉個🌰：分割"aac"。

1. 分割為 a + ac
2. 分割為 a + a + c，分割後，得到一組結果，再回溯到 a + ac
3. a + ac 中 ac 不是回文串，繼續回溯，回溯到 aac
4. 分割為稍長的回文串，分割為 aa + c 分割完成得到一組結果，再回溯到 aac
5. aac 不是回文串，搜尋結束

動畫描述

代碼實作

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        if(s==null||s.length()==0)
            return res;
        dfs(s,new ArrayList<String>(),0);
        return res;
    }

    public void dfs(String s,List<String> remain,int left){
        if(left==s.length()){  //判斷終止條件
            res.add(new ArrayList<String>(remain));  //添加到結果中
            return;
        }
        for(int right=left;right<s.length();right++){  //從left開始，依次判斷left->right是不是回文串
            if(isPalindroom(s,left,right)){  //判斷是否是回文串
                remain.add(s.substring(left,right+1));   //添加到目前回文串到list中
                dfs(s,remain,right+1);  //從right+1開始繼續遞歸，尋找回文串
                remain.remove(remain.size()-1);  //回溯，進而尋找更長的回文串
            }
        }
    }
    /**
    * 判斷是否是回文串
    */
    public boolean isPalindroom(String s,int left,int right){
        while(left<right&&s.charAt(left)==s.charAt(right)){
            left++;
            right--;
        }
        return left>=right;
    }
}      

我的專欄：

​​和程式員小吳一起學算法​​

❤️ 看完三件事：

如果你覺得這篇内容對你挺有啟發，我想邀請你幫我三個忙：

1. 點贊，讓更多的人也能看到這篇内容（收藏不點贊，都是耍流氓 -_-）
2. 關注我和專欄，讓我們成為長期關系
3. 關注公衆号「五分鐘學算法」，第一時間閱讀最新的算法文章，公衆号背景回複 1024 送你 50 本 算法程式設計書籍。