目錄
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 剪枝。
)
