131. Palindrome Partitioning

当一个dfs在for循环里，那么for循环的初始值写成i = start的时候，通常是想让递归在进入下一层的时候不从原来的位置开始（例如combination sum ii）。

但当我做到Palindrome Partitioning这题的时候，才发现start原来也是会增加的；因为通常start都只是用来标记i，但这题start本身也参与到了每次的dfs里。

isPalindrome(s, start, i)

这样一下子增大了很多思维难度。。

于是我又调试了一下，发现对于"aab"，dfs执行顺序大概是这样的：
start , i
0, 0
1, 1
2, 2 add to result
1, 1
1, 2
0, 0
0, 1
2, 2 add to result
0, 1
0, 2

所以，答案是这种：
[a, a, b], [aa, b]

这题我其实还是有点无法想象递归过程的，我能想到就是一个类似右上三角矩阵那么执行下去，对于终止条件 if (start == s.length()) ，我知道i会从start到s.length这么刷（被for控制着），但有点想不通为什么start会往复地从头到尾这么刷。但要明白，start会多次从0到尾刷，而不是只执行一次 。
再次理解04282017
早上又稍微想了一下，既然前三次递归start会从0到1再到2，也就说明i一定会start开始从0走到最后和从1，2走到最后。如此就往复多次了。

不必想，不必想。。

---

中午吃完饭的间隙写了一下这题的代码，是按照之前看过答案的印象里写的。调试了2次，AC了。

public class Solution {
        public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        backtrack(list, new ArrayList<String>(), s, 0);
        return list;
    }
    
    public void backtrack(List<List<String>> list, List<String> tempList, String s, int start) {
        if (start == s.length()) {
            list.add(new ArrayList<String>(tempList));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s , start, i)) {
                tempList.add(s.substring(start, i + 1));
                backtrack(list, tempList, s, 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;
    }

}

调试的第一次是，low<high改成了low<=high。
第二次是，if (isPalindrome(s , start, i)) 的判断，之前写成sPalindrome(s.substring(start , i+1) , start, i)了。