【Leetcode 每日一题】131. 分割回文串

问题背景

给你一个字符串 $s$，请你将分割成一些子串，使每个子串都是 回文串 。返回 $s$ 所有可能的分割方案。

数据约束

• $1\le s.length\le 16$
• $s$ 仅由小写英文字母组成

解题过程

经典回溯题，将分割的过程看作选择在字符之间的哪个位置添加分隔符。

具体实现

选或不选

class Solution {private final List<List<String>> res = new ArrayList<>();private final List<String> path = new ArrayList<>();private String s;public List<List<String>> partition(String s) {this.s = s;dfs(0, 0);return res;}private void dfs(int i, int start) {// 当前遍历到的位置已经达到字符串末尾，记录答案并返回if (i == s.length()) {res.add(new ArrayList<>(path));return;}// 处理不在当前位置添加分隔符的情况，字符串末尾处是一定要添加的if (i < s.length() - 1) {dfs(i + 1, start);}// 在当前位置添加分隔符，判断字串是是否回文if (isPalindrome(start, i)) {// 添加答案path.add(s.substring(start, i + 1));// 从下一个位置开始新的递归过程dfs(i + 1, i + 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;}
}

选哪一个

class Solution {private final List<List<String>> res = 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 res;}private void dfs(int i) {// 当前遍历到的位置已经达到字符串末尾，记录答案并返回if (i == s.length()) {res.add(new ArrayList<>(path));return;}// 讨论在当前状态下，后续每个可能添加分隔符的位置for (int j = i; j < s.length(); j++) {if (isPalindrome(i, j)) {// 添加答案path.add(s.substring(i, j + 1));// 从下一个位置开始新的递归过程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;}
}