力扣hot100 分割回文串 集合 dfs

Problem: 131. 分割回文串

思路

👨‍🏫 参考题解

Code

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {int n;//字符长度List<List<String>> res = new ArrayList<>();char[] ss;//字符数组public List<List<String>> partition(String s) {n = s.length();if (n == 0)return res;ss = s.toCharArray();dfs(0, new Stack<String>());return res;}
// idx 是当前未分割段的起点包含）
// path 是当前已分割的字符串集合private void dfs(int idx, Stack<String> path) {if (idx == n) //n以前的字符都分割了，结算{res.add(new ArrayList<String>(path));return;}for (int i = idx; i < n; i++) // i 枚举的是截取的位置{if (!check(idx, i))//不回文直接跳过continue;path.add(new String(ss, idx, i + 1 - idx));dfs(i + 1, path);// i 是截取的位置，i+1 是未截取段的起点path.pop();}}// 判断 ss[] 中 [l，r] 区间是否为回文子串，回文返回 trueprivate boolean check(int l, int r) {while (l < r)if (ss[l++] != ss[r--])return false;return true;}
}

💖 DP预处理版

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<String>> partition(String s) {int len = s.length();List<List<String>> res = new ArrayList<>();if (len == 0) {return res;}char[] charArray = s.toCharArray();// 预处理// 状态：dp[i][j] 表示 s[i][j] 是否是回文boolean[][] dp = new boolean[len][len];// 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]for (int right = 0; right < len; right++) {// 注意：left <= right 取等号表示 1 个字符的时候也需要判断for (int left = 0; left <= right; left++) {if (charArray[left] == charArray[right] && (right - left <= 2 || dp[left + 1][right - 1])) {dp[left][right] = true;}}}Deque<String> stack = new ArrayDeque<>();dfs(s, 0, len, dp, stack, res);return res;}private void dfs(String s, int index, int len, boolean[][] dp, Deque<String> path, List<List<String>> res) {if (index == len) {res.add(new ArrayList<>(path));return;}for (int i = index; i < len; i++) {if (dp[index][i]) {path.addLast(s.substring(index, i + 1));dfs(s, i + 1, len, dp, path, res);path.removeLast();}}}
}