微网站建设及微信推广方案,手机网站 ui,在国外服务器上做网站项目如何赚钱,牟平网站制作公司跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode:131. 分割回文串 给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是回文串。返回 s 所… 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode:131. 分割回文串 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文串。返回 s 所有可能的分割方案。 示例 1 输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2 输入s “a” 输出[[“a”]] 其实这题和前面的组合问题还是类似的只是这里加了个切割字符串并且判断是否回文的概念需要注意子串怎么切割这里是左闭右开的index~i 1这个区间的就是子串 public ListListString partition(String s) {ListListString res new ArrayList();backtracking(s, 0, new ArrayList(), res);return res;}private void backtracking(String s, int index, ListString path, ListListString res) {if (index s.length()) {res.add(new ArrayList(path));return;}for (int i index; i s.length(); i) {if (isPalindrome(s, index, i)) {path.add(s.substring(index, i 1));backtracking(s, i 1, path, res);path.remove(path.size() - 1);}}}private boolean isPalindrome(String s, int start, int end) {while (start end) {if (s.charAt(start) ! s.charAt(end)) {return false;}start;end--;}return true;}
