✨今日算法一题
分割回文串
文章目录
分割回文串
题目描述
思路详解
本题我们所采用的是回溯的方法解题。
这里利用栈的数据结构，进行解题。
首先第一层循环我们遍历数组，调用backtrack方法。
代码与结果
class Solution { public List<List<String>> partition(String s) { List<List<String>> res = new ArrayList<>(); backtrack(res, s, new ArrayList<String>()); return res; } private void backtrack(List<List<String>> res, String s, ArrayList<String> tmp) { if (s == null || s.length() == 0) res.add(new ArrayList<>(tmp)); for (int i = 1; i <= s.length(); i++) { if (isPalidrome(s.substring(0, i))) { // System.out.println(s.substring(0, i)); tmp.add(s.substring(0, i)); backtrack(res, s.substring(i, s.length()), tmp); tmp.remove(tmp.size() - 1); } } } private boolean isPalidrome(String sb) { int left = 0; int right = sb.length() - 1; while (left < right) { if (sb.charAt(left) != sb.charAt(right)) return false; left++; right--; } return true; } }
✨总结
本篇文章是本栏的最后一篇了，后期的算法刷题将更换为《牛客》刷题。
算法需要多加练习哦！！！
