LeetCode 131-分割回文串

题目链接：LeetCode131

欢迎留言交流，每天都会回消息。

class Solution {

    //用于存储最终返回的结果
    List<List<String>> rs = new ArrayList<>();
    //用于存储分割后的每一个字串
    ArrayList<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backTracking(s, new StringBuilder(), 0);
        return rs;
    }

    //s:传入的字符串
    //sb：分割后的字串
    //startIdx：记录分割的位置
    void backTracking(String s, StringBuilder sb, int startIdx){
        //终止条件：分割位置到最后时终止
        if(startIdx == s.length()){
            rs.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIdx; i < s.length(); i++){
            sb.append(s.charAt(i));
            if(check(sb)){
                path.add(sb.toString());
                //递归调用
                backTracking(s, new StringBuilder(), i + 1);
                //回溯
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean check(StringBuilder sb){
        for(int i = 0; i < sb.length()/2; i++){
            if(sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}