✍[LeetCode]dp131 分割回文串

完全看不懂是例题怎么切割的…..因此只求出了串中所有能够组成回文串的子串

传送门：https://leetcode-cn.com/problems/palindrome-partitioning/

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]

示例 2：

输入：s = “a” 输出：[[“a”]]

解题思路：动态规划

表示 能否构成回文串。若能取 true ，否则 false

状态转移方程：

                            ![](https://cdn.nlark.com/yuque/__latex/2a9735d22553e05a37f0316c8c42633b.svg#card=math&code=dp%5Bi%2C%20j%5D%3D%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bll%7D%0A%5Ctext%20%7B%20False%2C%20%7D%20%26%20i%20%5Cgeq%20j%20%5C%5C%0Adp%5Bi%2B1%20%5C%20%5D%5B%5C%20%20j-1%5D%20%E4%B8%94%20%28s%5Bi%5D%3Ds%5Bj%5D%29%2C%20%26%20%5Ctext%20%7B%20otherwise%20%7D%0A%5Cend%7Barray%7D%5Cright.&height=54&id=PyXFB)<br />                                      ![image.png](https://cdn.nlark.com/yuque/0/2021/png/2955945/1618197981395-2622aa21-d194-4dc1-a1cc-3b7c12132747.png#height=206&id=injXs&margin=%5Bobject%20Object%5D&name=image.png&originHeight=206&originWidth=350&originalType=binary&ratio=1&size=4830&status=done&style=none&width=350)
  - `i>=j` ，说明非法
  - `s[i+1...j-1]` 是回文串，且`s[i]=s[j]` ，那么必然 `s[i...j]` 构成回文串

代码

我的代码

public class Demo {
    //dp[i][j]代表从第i个字符到第j个字符能否构成回文
    //状态转移方程：dp[i][j]=dp[i+1][j-1]&&s[i]=s[j] (其中i<j)
    public static List<String> partition(String s) {
        if(s==null||s.length()==0)return null;
        List<String>list=new ArrayList<>();
        boolean [][]dp=new boolean[s.length()+1][s.length()+1];
        for (int i = 0; i <= s.length(); i++) dp[i][i]=true;//初始一个字符
        for (int i = s.length(); i >0 ; i--) {
            for (int j = i; j <= s.length(); j++) {
                if(j-i==1)dp[i][j]=(s.charAt(i-1)==s.charAt(j-1));//表示两个字符
                else if(i!=j)dp[i][j]=(dp[i+1][j-1]&&s.charAt(i-1)==s.charAt(j-1));//其他多个字符
                if(dp[i][j]){
                    list.add(s.substring(i-1,j));//同C++ 左闭右开
                }
            }
        }
        return list;
    }
    public static void main(String[] args) {
        System.out.println(partition("adadadad"));
    }
}