題意理解：

? ? ? ? 分割回文子串，可以看作是劃分連續的字幕組合——所以也可以用回溯的方法來解決

? ? ? ? 每個位置選與不選——該位置切割|不切割

? ? ? ? 對于每一段子串——>判斷是否是回文串：

? ? ? ? ? ? ? ? 是： 繼續切割

? ? ? ? ? ? ? ? 不是：? ? ? ? 剪枝

解題方法：

? ? ? ? 回溯，難點在于如何理解切割位置——將其抽象為樹結構

? ? ? ? 切割位置：切割位置會比數組長度+1

1.暴力回溯+剪枝優化

?準備條件：1.判斷子串是回文？

? ? ? ? ? ? ? ? ? ?2.遞歸|回溯

回溯三個關鍵步驟：

? ? ? ? 1.確定返回值和參數列表： void backtracking()

? ? ? ? 2.終止條件:

? ? ? ? ? ? ? ? ? ?是回文且切至字符串尾部——結束，收集結果

? ? ? ? 3.單層邏輯|做好回溯步驟：

????????????????子串是不回文——剪枝：提前剪枝，所以分隔到字符串尾部的一定都是合法的回文分割。

 List<List<String>> result=new ArrayList<>();LinkedList<String> path=new LinkedList<>();public List<List<String>> partition(String s) {backtracking(s,0);return result;}public void backtracking(String s,int startIndex){//終止條件if(startIndex>=s.length()){result.add(new ArrayList<>(path));return;}//單層邏輯for(int i=startIndex;i<s.length();i++){//獲取子串并判斷if(isPalindrome(s,startIndex,i)){path.add(s.substring(startIndex,i+1));backtracking(s,i+1);path.removeLast();}else{//不是回文——剪枝continue;}}}//左閉右閉判斷子串是否是回文public boolean isPalindrome(String s,int start,int end){while(start<=end){if(s.charAt(start)==s.charAt(end)){start++;end--;}else{return false;}}return true;}

2.分析

時間復雜度：O()

空間復雜度：O()? ????????n是元素個數

????????使用 O(n) 的棧空間以及 O(n)的用來存儲當前字符串分割方法的空間。