🙁Palindrome partitioning

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

这个思路还挺经典的不应该想不到，感觉是被取substring和check is palindrome的时间复杂度吓到了

class Solution {
    private List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String s) {
        dfs(s, 0, new ArrayList<>());
        return ans;
    }
    private void dfs(String s, int index, List<String> path) {
        if (index == s.length()) {
            ans.add(new ArrayList<>(path));
        }
        for (int i = index + 1; i <= s.length(); i++) {
            String substring = s.substring(index, i);
            if (isPalindrome(substring)) {
                path.add(substring);
                dfs(s, i, path);
                path.remove(path.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String str) {
        int i = 0;
        int j = str.length() - 1;
        while (i < j) {
            if (str.charAt(i) != str.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}