LeetCode-131分割回文串-中等

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

回文串 是正着读和反着读都一样的字符串。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

1 <= s.length <= 16s 仅由小写英文字母组成 代码Java

List> ans = new ArrayList<>();
List temp = new ArrayList<>();
int len = 0;  // 用于判断  可用start代替
public List> partition(String s) {
    if (s.length() == 0 || s == null) return ans;
    backtracking(s, 0);
    return ans;
}

public void backtracking(String s, int start) {
    if (len >= s.length()) {
        ans.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i < s.length(); i++) {
        String str = s.substring(start, i + 1);
        if (isPalidrome(s, start, i)) {
            len += str.length();
            temp.add(str);
        } else {
            continue; // 当不能切割时 则无需递归， 直接跳过  ！！！！！
        }
        backtracking(s, i + 1);
        len -= str.length();
        if (!temp.isEmpty()) {
            temp.remove(temp.size() - 1);
        }
    }
}

// 双指针判断回文串
public boolean isPalidrome(String str, int left, int right) {
    while (left < right) {
        if (str.charAt(left) != str.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}