分割回文串+最长回文子字符串

分割回文串

解题方法:回溯法

1. 画出递归树

2. 根据递归树开始编码

1. 每个节点表示剩余的没有扫描到的字符串，产生分支是截取了剩余字符串的前缀；

• 如果前缀字符串是回文，则表示可以产生分支和节点
• 如果前缀字符串不是回文，则不产生分支和节点，这一步是剪枝操作

2. 在叶子节点是空字符串的时候结算，此时从根节点到叶子节点的路径，就是结果集里的一个结果，使用深度优先遍历，记录下所有可能的结果。

• 采用一个路径变量path搜索，path全局使用一个（注意结算的 时候，需要生成一个拷贝），因此在递归执行方法结束以后需要回溯，即将递归之前添加进来的元素拿出去

代码实现 

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if(s == null || s.equals("")){
            return res;
        }
        List<String> path = new ArrayList<>();
        helper(s, 0, s.length() - 1, path);
        return res;
    }
    public void helper(String s, int start, int end, List<String> path){
        //递归出口（注意:这里是end+1）
        if(start == (end + 1)){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i <= end; i++){
            //如果s[start, i]不为空，则直接试探下一个位置
            if(!checkPalindroms(s, start, i)){
                continue;
            }
            path.add(s.substring(start, i + 1));
            helper(s, i + 1, end, path);
            path.remove(path.size() - 1);
        }
    }
    public boolean checkPalindroms(String s, int left, int right){
        if(s == null || s.equals("")){
            return true;
        }
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}

最长回文子字符串

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() < 1){
            return "";
        }
        int res = Integer.MIN_VALUE;
        int begin = 0;//用来保存上一个最长子字符串的开始位置
        int end = 0;//用来保存上一个最长子字符串的结束位置
        for(int i = 0; i < s.length(); i++){
            int l = expandAroundCenter(s, i, i);
            int r = expandAroundCenter(s, i, i + 1);
            int len = Math.max(l, r);
            if(len > ((end - begin) + 1)){
                begin = i - (len - 1) / 2;
                end = i + (len) / 2;
            }
        }
        return s.substring(begin, end + 1);
    }
    public int expandAroundCenter(String s, int left, int right){
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left --;
            right ++;
        }
        return Math.max(right - left - 1, 0);
    }
}