Leetcode-131.Palindrome Partitioning [C++][Java]

目录

一、题目描述

二、解题思路

【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;}
}