题解 | #所有的回文子串I#

知识点：字符串，回溯

要列举所有子字符串为回文串的情况，首先就要考虑到使用回溯的方法来实现。每次寻找一个回文子串，然后保存下来，接着在剩余字符串中寻找下一个回文子串，直至遍历完所有的回文子串，且当前刚好到达字符串尾部，此时，将此次遍历的结果保存下来。使用回溯，找到所有可能的结果。

对于回文串的判断，我们可以使用双指针的方法，分别判断首尾两个字符是否相等，前后指针依次向中间靠拢，直至重合。

Java题解如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串二维数组
     */
    private List<List<String>> list = new ArrayList<>();
    private String s;

    public String[][] partition (String s) {
        // write code here
        this.s = s;
        backTracking(new ArrayList<>(), 0);
        String[][] res = new String[list.size()][];
        for(int i = 0; i < list.size(); i++) {
            List<String> tmp = list.get(i);
            res[i] = new String[tmp.size()];
            for(int j = 0; j < tmp.size(); j++) {
                res[i][j] = tmp.get(j);
            }
        }
        return res;
    }

    private void backTracking(List<String> tmp, int index) {
        if(index == s.length()) {
            list.add(new ArrayList<>(tmp));
            return;
        }
        for(int i = index + 1; i <= s.length(); i++) {
            if(check(s.substring(index, i))) {
                tmp.add(s.substring(index, i));
                backTracking(tmp, i);
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    private boolean check(String s) {
        for(int i = 0; i < s.length() / 2; i++) {
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}