## 131. Palindrome Partitioning 原

cofama

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

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> v;
vector<string> part;
findPartition(s, 0, v, part);
return v;
}

private:
void findPartition(string &s, int start, vector<vector<string>> &v, vector<string> &part) {
for(int i=start; i<s.length(); i++) {
if(i==start || isPalindrome(s, start, i)) {
part.push_back(s.substr(start, i-start+1));
if(i==s.length()-1) v.push_back(part);
else findPartition(s, i+1, v, part);
part.pop_back();
}
}
}

bool isPalindrome(string &s, int start, int end) {
while(start<=end) {
if(s[start++]!=s[end--]) return false;
}
return true;
}
};
``````

``````public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;
}
}
}
helper(res, new ArrayList<>(), dp, s, 0);
return res;
}

private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
if(pos == s.length()) {
return;
}

for(int i = pos; i < s.length(); i++) {
if(dp[pos][i]) {
helper(res, path, dp, s, i+1);
path.remove(path.size()-1);
}
}
}
}
``````

dp[j][i]表示第j个字符到第i个字符的子串是否为回文，其中确定dp[j][i]的值又可以利用dp[j+1][i-1]的结果，用到了动态规划的思想。这样helper的时间复杂度依然为O(2^n)，判断回文的复杂度为O(n^2)，整体复杂度降到了O(2^n)。

### cofama

LeetCode 131 Palindrome Partitioning

LeetCode 131 Palindrome Partitioning 划分字符串，得到每一个子串都是回文串，输出所有的方案。 思路是，先将所有的回文子串都找出来，记录下左右端点。 然后DFS这些子串就可以了。...

Shendu.cc
2018/11/07
0
0
[LeetCode] Shortest Palindrome 最短回文串

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this tran......

2017/12/02
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自： https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0

2017/09/28
0
0
python之扩展

17.2 非常简单的途径：Jython 和 IronPython 一个简单的java类 public class JythonTest{ public void greeting(){ System.out.println("Hello,world"): } } java编译器编译，例如javac \$ja......

2015/06/13
0
0

29分钟前
3
0

forespider
40分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index（“待截取的字符串”，“截取数据依据的字符”，截取字符的位置N） 第三个参数可正，可负。正数表示索引字符前面的字符串，负数...

echojson
40分钟前
1
0

50分钟前
2
0

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

52分钟前
3
0