131. Palindrome Partitioning

https://leetcode-cn.com/problems/palindrome-partitioning/

（图片来源https://leetcode-cn.com/problems/palindrome-partitioning/

）

递归

public List<List<String>> partition(String str) {
        List<List<String>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), str, 0);

        return res;
    }

    private void backtrack(List<List<String>> res, List<String> tempList, String str, int start){
        if(start == str.length()) {
            res.add(new ArrayList<>(tempList));
        } else {
            for(int i = start; i < str.length(); i++){
                if(isPalindrome(str, start, i)) {

                    tempList.add(str.substring(start, i + 1));  // 字符串范围[start, i+1)
                    backtrack(res, tempList, str, i + 1);
                    tempList.remove(tempList.size() - 1);
                }
            }
        }
    }


    private boolean isPalindrome(String s, int low, int high){
        while(low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }

        return true;
    }