131. Palindrome Partitioning

3/27/2018 update:
用index肯定比用substring 要快。
1/22/2018
Solution:

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res=new ArrayList<>();
        if (s == null || s.length() == 0) return null;
        helper(res, new ArrayList<>(), s);
        return res;
    }
    
    private void helper(List<List<String>> res, List<String> temp, String s) {
        if (s.length() == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
            
        
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome(s.substring(0, i + 1))) {
                temp.add(s.substring(0, i + 1));
                helper(res, temp, s.substring(i + 1));
                temp.remove(temp.size()- 1);
            }
        }
    }
    
    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while(l < r) {
            if (s.charAt(l) != s.charAt(r)) 
                return false;
            l++;
            r--;
        }
        return true;
    }
}

--------------------------------------------------------------------------------------------------------------------------

思路：
画个图来分析一下。下划线表示当前坚持的substring。第一层是abcd整个string partition。第二层，startindex++,  所以只考虑bcd partition。