【LeetCode】131. Palindrome Partitioning 解题报告（Python & C++）

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

目录

题目描述题目大意解题方法回溯法 日期

题目地址：https://leetcode.com/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:

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

题目大意

找出一个字符串可以构成的所有可能回文子字符串。

解题方法

回溯法

看到所有可能的结果的时候，一般想到回溯。

这个题和之前的回溯有个差别，那就是继续开始回溯的条件是目前的结果已经是回文串。然后从后面的字符开始继续回溯。感觉回溯都是套路，80%的代码可以通用的，最好背下来。

特别注意切片的位置，以及path + [s[:i]]产生了新的list中，所以append时候才有效。

class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ self.isPalindrome = lambda s : s == s[::-1] res = [] self.helper(s, res, []) return res def helper(self, s, res, path): if not s: res.append(path) return for i in range(1, len(s) + 1): #注意起始和结束位置 if self.isPalindrome(s[:i]): self.helper(s[i:], res, path + [s[:i]])

和上面思想相同的经典C++回溯法写法如下：

class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> res; helper(s, res, {}); return res; } void helper(string s, vector<vector<string>>& res, vector<string> path) { if (s.size() == 0) { res.push_back(path); return; } for (int i = 1; i <= s.size(); i++) { string pre = s.substr(0, i); if (isPalindrome(pre)) { path.push_back(pre); helper(s.substr(i), res, path); path.pop_back(); } } } bool isPalindrome(string s) { if (s.size() == 0) return true; int start = 0, end = s.size() - 1; while (start <= end) { if (s[start] != s[end]) return false; start ++; end --; } return true; } };

如果不使用新的函数，只是用题目给的函数也能通过，唯一需要注意的是，当字符串长度是0的时候返回的是空，那么我们没办法在for循环里面进行遍历，所以新增上一个空字符串，最后再去掉。

class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> res; if (s.size() == 0) return res; for (int i = 1; i <= s.size(); i++) { string pre = s.substr(0, i); if (isPalindrome(pre)) { vector<vector<string>> next = partition(s.substr(i)); if (next.size() == 0) next.push_back({""}); for (vector<string> vs : next) { vector<string> path; path.push_back(pre); for (string s : vs) { if (s == "") continue; path.push_back(s); } res.push_back(path); } } } return res; } bool isPalindrome(string s) { if (s.size() == 0) return true; int start = 0, end = s.size() - 1; while (start <= end) { if (s[start] != s[end]) return false; start ++; end --; } return true; } };

日期

2018 年 3 月 15 日 ——雾霾消散，春光明媚 2018 年 12 月 21 日 —— 一周就要过去了