代码随想录——分割回文串（Leetcode 131）

题目链接

回溯

class Solution {List<List<String>> res = new ArrayList<List<String>>();List<String> list= new ArrayList<String>();public List<List<String>> partition(String s) {backtracking(s, 0);return res;}public void backtracking(String s, int startIndex){if(startIndex >= s.length()){res.add(new ArrayList<>(list));return;}for(int i = startIndex; i < s.length(); i++){// 如果是回文数，则继续回溯if(is(s, startIndex, i)){list.add(s.substring(startIndex, i + 1));}else{continue;}backtracking(s, i + 1);list.removeLast();}}// 判断回文数public boolean is(String s, int start, int end){for(int i = start, j = end; i < j; i++, j--){if(s.charAt(i) != s.charAt(j)){return false;}}return true;}
}