Open youngyangyang04 opened 3 months ago
private void backtracking(String s, int start) {
if (start >= s.length()) {
paths.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
path.add(s.substring(start, i + 1));
backtracking(s, i + 1);
path.remove(path.size() - 1);
}
}
}
// 深度1: backtracking("aab", 0), path = ""
i = 0:"a" 是回文串, path = ["a"],递归 backtracking("aab", 1),回溯,path = []
i = 1:"aa" 是回文串, path = ["aa"],递归 backtracking("aab", 2),回溯,path = []
i = 2:"aab" 不是回文串, 停止遍历(剪枝)
// 深度2: 例: backtracking("aab", 1), path = ["a"]
i = 1:"a" 是回文串, path = ["a","a"],递归 backtracking("aab", 2),回溯,path = ["a"]
i = 2:"ab" 不是回文串, 停止遍历(剪枝)
// 深度3: 例: backtracking("aab", 2), path = ["a","a"]
i = 2:"b" 是回文串, path = ["a","a","b"],递归 3 >= 3,加入并返回。回溯,path = ["a","a"]
https://www.programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html