131. Palindrome Partitioning

🟠   🔖  字符串 动态规划 回溯  🔗 LeetCode

题目

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning ofs.

Example 1:

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"

Output: [["a"]]

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

题目大意

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

回文串 是正着读和反着读都一样的字符串。

解题思路

这是一个典型的回溯问题，需要穷举所有可能的分割方式，并且保证每个分割出来的子串都是回文串。以下是解题思路：

1. 使用回溯法，定义一个 track 数组来存储当前的分割方案，以及一个 res 数组来存储所有的合法分割方案。
2. 从字符串的起始位置开始，逐步截取子串，判断截取的子串是否是回文串。
3. 如果是回文串，则将该子串加入 track 数组中，然后递归调用，继续向后截取子串。
4. 如果不是回文串，则回溯到上一层，尝试其他的分割方案。
5. 当截取到字符串的末尾时，将当前的 track 数组加入 res 数组，表示找到了一种合法的分割方案。

代码

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
	let res = [];
	let track = [];

	// 判断字符串是否是回文字符串
	const isPalindrome = (str) => {
		let left = 0;
		let right = str.length - 1;
		while (left < right) {
			if (str[left] !== str[right]) {
				return false;
			}
			left++;
			right--;
		}
		return true;
	};

	const backtrack = (start) => {
		// 截取到了字符串的末尾，代表找到了一种合法的截取方式
		if (start == s.length) {
			res.push([...track]);
			return;
		}
		for (let i = start; i < s.length; i++) {
			// 截取从索引 start 到索引 i + 1（不包括 i + 1）的子串
			const str = s.substring(start, i + 1);
			if (isPalindrome(str)) {
				track.push(str);
				backtrack(i + 1);
				track.pop();
			}
		}
	};
	backtrack(0);
	return res;
};

相关题目

相关题目

• 132. 分割回文串 II
• 1745. 回文串分割 IV
• 2472. 不重叠回文子字符串的最大数目

- [132. 分割回文串 II](https://leetcode.com/problems/palindrome-partitioning-ii)
- [1745. 回文串分割 IV](https://leetcode.com/problems/palindrome-partitioning-iv)
- [2472. 不重叠回文子字符串的最大数目](https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings)