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"] ]
dp[i][j]=1表示str(i~j)可以是回文。
if dp[i+1][j-1] == 1 && s[i]==s[j]; dp[i][j] = 1;
N^2扫一遍。
然后根据dp[i][j] = 1等价于 (i,j)是一条边。(i,j) 与 (j+1, x)相连。
则就变成了有向图。
然后遍历图,从0->len-1。DFS一遍。
class Solution { public: vector<vector<int> > v; int n; string org; vector<vector<string>> partition(string s) { int len = s.size(); n = len; org = s; int dp[len][len] ; memset(dp, 0, sizeof(dp)); for (int i = 0; i < len; i++) { dp[i][i] = 1; if (i < len - 1 && s[i] == s[i+1]) dp[i][i+1] = 1; } for (int l = 2; l < len; l++) { for (int i = 0; i < len; i++) { int j = i+l; if (j >= len) continue; if (dp[i+1][j-1] == 1 && s[i] == s[j]) dp[i][j] = 1; } } v.clear(); v.resize(len); for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { if (dp[i][j] == 1) v[i].push_back(j); } } vector<vector<string> > res; vector<string> str; f(res, str, -1); return res; } void f(vector<vector<string> >& res, vector<string>& str, int cur) { if (cur == n - 1) { res.push_back(str); return; } int next = cur+1; for (int i = 0; i < v[next].size(); i++) { str.push_back(org.substr(next, v[next][i]-next+1)); f(res, str, v[next][i]); str.pop_back(); } } };
相关推荐
python python_leetcode题解之131_Palindrome_Partitioning
python python_leetcode题解之132_Palindrome_Partitioning_II
javascript js_leetcode题解之131-palindrome-partitioning.js
javascript js_leetcode题解之132-palindrome-partitioning-ii.js
1. **Palindrome Partitioning (mine).cpp** - 这个文件是关于LeetCode的第131题“回文分割”。该问题要求将一个字符串分割成多个回文子串。解冑通常涉及深度优先搜索或动态规划,寻找所有可能的分割方案并检查是否...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once/twice... - count
leetcode力扣是什么 leetcode-按类别 看了一些leetcode刷题指南,总结一下两个重点,一是最好按照类别刷题,总结思路;...Partitioning (hard) 212 Word Search II (hard) DFS /二叉树 the difference between df
Palindrome_Partitioning DP,避免递归调用,利用数组储存已算出来的数值,由后向前逐渐增加字符串处理 Palindrome_Partitioning_2 同上 Sum_Root_to_Leaf_Numbers DFS Surrounded_Regions 由四周‘O’开始向内检索...
gas station leetcode 在牛客网上的在线编程...palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
分割回文串(Palindrome Partitioning)**:这是一个关于字符串处理的题目,要求将一个字符串分割成若干个回文子串。主要涉及的算法是深度优先搜索(DFS),通过递归的方式检查所有可能的分割方案,判断是否都是回文。 ...
3. 题目131 - "Palindrome Partitioning" 这是一道回文子串分割问题,要求将一个字符串分割成多个回文子串。常见的解法是动态规划,创建一个二维数组来存储子问题的最优解。在Java中,可以使用StringBuilder和...
对于更高级的题目,可能会涉及图论或动态规划,比如`0131_palindrome_partitioning.py`可能涉及回文子串分割,这通常会用到动态规划来避免重复计算。 在PythonAlgo项目中,每个问题的解决方案都提供了清晰的思路和...