LeetCode 题解（152）: Palindrome Partitioning

本文主要是介绍LeetCode 题解（152）: Palindrome Partitioning，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [["aa","b"],["a","a","b"]]

题解：

递归， Backtracing。仅当当前子串为Palindrome时，递归后半。

C++版：

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

Java版：

public class Solution {public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<List<String>>();List<String> output = new ArrayList<String>();recursion(s, 0, output, result);return result;}void recursion(String s, int start, List<String> output, List<List<String>> result) {if(start == s.length()) {ArrayList<String> temp = new ArrayList<>();temp.addAll(output);result.add(temp);return;}for(int i = start; i < s.length(); i++) {if(isPalindrome(s, start, i)) {output.add(s.substring(start, i+1));recursion(s, i + 1, output, result);output.remove(output.size()-1);}}}public boolean isPalindrome(String s, int start, int end) {while(start < end) {if(s.charAt(start++) != s.charAt(end--))return false;}return true;}
}

Python版：

class Solution:# @param {string} s# @return {string[][]}def partition(self, s):result = []output = []self.recursion(s, 0, output, result)return resultdef recursion(self, s, start, output, result):if start == len(s):result.append(copy.copy(output))for i in range(start, len(s)):if self.is_palindrome(s, start, i):output.append(s[start:i+1])self.recursion(s, i + 1, output, result)output.pop()def is_palindrome(self, s, start, end):while start < end:if s[start] != s[end]:return Falsestart += 1end -= 1return True

这篇关于LeetCode 题解（152）: Palindrome Partitioning的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---