当前位置：首页 > news >正文

【算法笔记】LCR 086. 分割回文串

news 2025/8/10 15:16:30

在这里插入图片描述
基本思想是使用回溯法，回溯法都可以将问题划分为一个解空间树：假设字符串s为"aab"，那么我们可以使用深度优先搜索去构建解空间树：

dfs遍历出来的第一个序列是[a, a, b]，显然该序列都是回文子串，接着回溯，遍历下一个序列，为[a, ab]，不是回文子串，去除…如此往下遍历，将符合要求的序列加入到结果集res中，直到遍历整个解空间树

此题的重要思想有两个：
Java中的List变量存储的是List的地址，而非List本身，因此可以构建一个path列表，用于存储当前已经遍历的序列，当dfs向下遍历的时候则将新遍历的字符串加入path中；当向上回溯的时候，可以将path中的最后一个元素remove掉，从而恢复到上一个遍历状态

class Solution {public List<String> path = new ArrayList<>();public List<List<String>> result = new ArrayList();public void f(String str, int start){if (start >= str.length()){// 防止深复制导致的将List地址存入result，需要新建Listresult.add(new ArrayList<>(path));}for (int i = start; i < str.length(); i++) {if (isPalindrome(str, start, i)){path.add(str.substring(start, i+1));}elsecontinue;f(str, i+1);path.remove(path.size()-1); // 回溯}}public boolean isPalindrome(String s,int start,int end){//start从左到右，end从右到左，判断前后是否一致for(int i=start,j=end;i<j;i++,j--){if(s.charAt(i)!=s.charAt(j)){return false;}}return true;}public String[][] partition(String s) {f(s, 0);int rows = result.size();String[][] ret = new String[rows][];for (int i = 0; i < rows; ++i) {int cols = result.get(i).size();ret[i] = new String[cols];for (int j = 0; j < cols; ++j) {ret[i][j] = result.get(i).get(j);}}return ret;}
}