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

问题背景

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

数据约束 1 ≤ s . l e n g t h ≤ 16 1 \le s.length \le 16 1≤s.length≤16 s s 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; } }