LeetCode：131.分割回文串（DPJava）

目录

131. 分割回文串

题目描述：

实现代码与解析：

动态规划

原理思路：

---

131. 分割回文串 题目描述：

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

示例 1：

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

示例 2：

输入：s = "a" 输出：[["a"]]

提示：

1 <= s.length <= 16s 仅由小写英文字母组成 实现代码与解析： 动态规划 import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { private int n; private boolean[][] f; private List<List<String>> res = new ArrayList<>(); private List<String> list = new ArrayList<>(); public List<List<String>> partition(String s) { n = s.length(); f = new boolean[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(f[i], true); } for (int i = n -1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j) && f[i + 1][j - 1]) { f[i][j] = true; } else { f[i][j] = false; } } } dfs(s, 0); return res; } private void dfs(String s, int cur) { if (cur == n) { res.add(new ArrayList<String>(list)); return ; } for (int i = cur; i < n; i++) { if (f[cur][i]) { list.add(s.substring(cur, i + 1)); dfs(s, i + 1); list.remove(list.size() - 1); } } } } 原理思路：

        C++版Leetcode：131. 分割回文串（C++）_代码backtrack(s, 0)是什么意思-CSDN博客，

        f[i][j]含义是：下标 i 到 j 字符串是否为回文。单个字母也为回文，所以初始化true。判断如果char[i] == char[j] 并且 f[i + 1][j - 1]为true，说明f [ i ] [ j ] 为回文。

        然后dfs遍历即可。同时用 f 剪枝。