当前位置：首页 > news >正文

leetcode hot100【LeetCode 131.分割回文串】java实现

news 2024/11/13 12:42:55

LeetCode 131.分割回文串

题目描述

给定一个字符串 s，将 s 分割成若干个长度相等的子串，使得每个子串都是回文串。你需要找出所有可能的分割方案。

示例 1:

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

示例 2:

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

Java 实现代码

import java.util.*;public class Solution {public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<>();backtrack(s, 0, new ArrayList<>(), result);return result;}private void backtrack(String s, int start, List<String> path, List<List<String>> result) {// 如果已经遍历完所有字符，说明已经找到一个合法的分割方案if (start == s.length()) {result.add(new ArrayList<>(path));  // 复制当前路径加入结果return;}// 从当前位置开始，尝试所有可能的子串for (int end = start + 1; end <= s.length(); end++) {String substring = s.substring(start, end);// 如果当前子串是回文串，则继续递归if (isPalindrome(substring)) {path.add(substring);backtrack(s, end, path, result);  // 递归处理剩下的部分path.remove(path.size() - 1);  // 回溯，移除最后一个子串}}}// 判断一个子串是否为回文串private boolean isPalindrome(String s) {int left = 0, right = s.length() - 1;while (left < right) {if (s.charAt(left++) != s.charAt(right--)) {return false;}}return true;}
}

解题思路

回溯法：

这个问题可以用回溯法来解决。回溯的核心思想是将问题分解为子问题，并不断尝试在当前的选择基础上做出决策。每当我们尝试一个分割方案时，我们检查当前子串是否是回文串，如果是，则继续递归。

回文串判定：

回文串的判定是一个常见的操作，对于给定的字符串 s 和某个子串 s[left...right]，只需要检查 s[left] == s[right] 且 s[left+1...right-1] 也是回文的。

递归和回溯：

我们从字符串的第一个字符开始，尝试分割每一段回文子串，并将其加入到当前分割结果中。如果整个字符串都能被分割为回文串，则将该分割方案加入到最终结果中。
如果当前子串不是回文串，则回溯并尝试下一个子串。

具体步骤：

定义一个回溯函数 backtrack(start, path)，start 是当前遍历的位置，path 保存当前分割的回文子串。
对于每个起点 start，遍历从 start 到字符串末尾的所有子串，如果该子串是回文串，则将其加入 path 中，并递归调用 backtrack 处理下一个起点。
递归结束时，将当前分割方案添加到结果列表中。