LeetCode：131. 分割回文串（DP Java）

目录

131. 分割回文串

题目描述：

实现代码与解析：

动态规划

原理思路：

---

131. 分割回文串

题目描述：

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

实现代码与解析：

动态规划

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 剪枝。