网站共用数据库今日新闻网

我对回溯题还是不清楚，尤其是还原现场这部分。
这道题是从答案角度出发，考虑如何分割。参考Leetcode的解题。

在这个回溯过程中：

1. 每走一步，对于每个逗号，有两个选项：要么不选它，要么选它。每个选项就像是在树上走一个分支。
2. 但是我们一次只能处理一个分支，计算完了【不选】的分支，就要倒回去，回到前面去处理另外一个【选】的分支。倒回去之前加到 path 中的数据是垃圾数据，要及时清除掉。

class Solution {private final List<List<String>> ans = new ArrayList<>();private final List<String> path = new ArrayList<>();private String s;public List<List<String>> partition(String s) {this.s =s;dfs(0);return ans;}private void dfs(int i){if(i==s.length()){ans.add(new ArrayList<>(path));return;}//i为子串开始的位置，j为子串结束的位置for(int j=i; j<s.length();j++){if(isPalindrome(i,j)){path.add(s.substring(i,j+1));//对s的剩余部分进行分割dfs(j+1);//回溯path.remove(path.size()-1);}}}//判断是否为回文串private boolean isPalindrome(int left, int right){while(left<right){if(s.charAt(left++)!=s.charAt(right--)){return false;}}return true;}
}