目录
一、题目描述
二、解题思路
【C++】
【Java】
Leetcode-131.Palindrome Partitioninghttps://leetcode.com/problems/palindrome-partitioning/description/131. 分割回文串 - 力扣(LeetCode)131. 分割回文串 - 给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1:输入:s = "aab"输出:[["a","a","b"],["aa","b"]]示例 2:输入:s = "a"输出:[["a"]] 提示: * 1 <= s.length <= 16 * s 仅由小写英文字母组成
https://leetcode.cn/problems/palindrome-partitioning/description/
一、题目描述
Given a string s
, partition s
such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s
.
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.
二、解题思路
-
时间复杂度:O(n⋅2^n)
-
空间复杂度:O(n^2)
【C++】
class Solution {
private:void dfs(const string& s, int start, vector<string>& pat, vector<vector<string>>& res) {if (start == s.length()) {res.push_back(pat);}else {for (int i = start; i < s.length(); i++) {if (isPalindrome(s, start, i)) {pat.push_back(s.substr(start, i - start + 1));dfs(s, i + 1, pat, res);pat.pop_back();}}}}bool isPalindrome(const string& s, int l, int r) {while (l <= r) if (s[l++] != s[r--]) return false;return true;}public:vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> pat; dfs(s, 0, pat, res);return res;}
};
【Java】
class Solution {private void dfs(String s, int start, List<String> pat, List<List<String>> res) {if (start == s.length()) {res.add(new ArrayList<>(pat));}else {for (int i = start; i < s.length(); i++) {if (isPalindrome(s, start, i)) {pat.add(s.substring(start, i + 1));dfs(s, i + 1, pat, res);pat.remove(pat.size() - 1);}}}}private boolean isPalindrome(String s, int l, int r) {while (l <= r) if (s.charAt(l++) != s.charAt(r--)) return false;return true;}public List<List<String>> partition(String s) {List<List<String>> res = new ArrayList<>();List<String> pat = new ArrayList<>();dfs(s, 0, pat, res);return res;}
}