131. 分割回文串

[rocksc30]

class Solution {
    private List<List<String>> ans = new ArrayList<>();
    private Deque<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        helper(s, 0);
        return ans;
    }
    private void helper(String s, int index){
        if (index == s.length()) ans.add(new ArrayList<>(path));
        for (int i = index; i < s.length(); i++){
            if (isPalindrome(s, index, i))
                path.add(s.substring(index, i + 1));
            else
                continue;
            helper(s, i + 1);
            path.removeLast();
        }
    }
    private boolean isPalindrome(String s, int left, int right){
        while (left < right){
            if (s.charAt(left++) != s.charAt(right--)){
                return false;
            }
        }
        return true;
    }
}