网站建设费可以一次性冲费用吗,开展农业信息网站建设工作,wordpress tag链接优化,给金融公司群做网站合法吗我对回溯题还是不清楚#xff0c;尤其是还原现场这部分。 这道题是从答案角度出发#xff0c;考虑如何分割。参考Leetcode的解题。
在这个回溯过程中#xff1a;
每走一步#xff0c;对于每个逗号#xff0c;有两个选项#xff1a;要么不选它#xff0c;要么选它。每个…我对回溯题还是不清楚尤其是还原现场这部分。 这道题是从答案角度出发考虑如何分割。参考Leetcode的解题。
在这个回溯过程中
每走一步对于每个逗号有两个选项要么不选它要么选它。每个选项就像是在树上走一个分支。但是我们一次只能处理一个分支计算完了【不选】的分支就要倒回去回到前面去处理另外一个【选】的分支。倒回去之前加到 path 中的数据是垃圾数据要及时清除掉。
class Solution {private final ListListString ans new ArrayList();private final ListString path new ArrayList();private String s;public ListListString partition(String s) {this.s s;dfs(0);return ans;}private void dfs(int i){if(is.length()){ans.add(new ArrayList(path));return;}//i为子串开始的位置j为子串结束的位置for(int ji; js.length();j){if(isPalindrome(i,j)){path.add(s.substring(i,j1));//对s的剩余部分进行分割dfs(j1);//回溯path.remove(path.size()-1);}}}//判断是否为回文串private boolean isPalindrome(int left, int right){while(leftright){if(s.charAt(left)!s.charAt(right--)){return false;}}return true;}
}
