新博文地址:
[leetcode]Palindrome Partitioning II
Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
将字符串切成片,要求是每一段都是回文串。拿到这道题的第一反应就是用DP,但是状态转移方程实在是想不出来。。。。所以看了一下别人的算法,是厉害。
具体算法:
1. 确定字符串s的最小切割数
2. 则字符串 ‘#’ + s 的最小切割数则是遍历s,如果遇到‘#’(假设#在s中的索引是i)则'#' + s的切割数即为s.substring(1) 的切割数或者+ 1(如果#出现在s的最后一个位置,则不需要+1)
因此状态转移方程为 result[i] = min(result[i] , result[j + 1] + 1) (当j + 1 != length时)和result[i] = min(result[i] , result[j + 1] )(当j + 1 == length时)
这个算法很腻害的是,没有计算某个字符子串是否是回文的,而是用一个二维数组来标记是否是回文,很值得借鉴。
不罗嗦了,代码如下:不明白可以吐槽
public int minCut(String s) { if( s == null || s.length() < 2){ return 0; } int[] result = new int[s.length() + 1]; boolean[][] map = new boolean[s.length()][s.length()]; for(int i = s.length() - 1; i >=0 ; i--){ result[i] = s.length() - i - 1; for(int j = i ; j < s.length(); j++){ if(s.charAt(i) == s.charAt(j)){ if(j - i <= 1 || map[i + 1][j - 1] == true){ map[i][j] = true; if(j == s.length() - 1){ result[i] = Math.min(result[i], result[j + 1]); } result[i] = Math.min(result[i], result[j + 1] + 1); } } } } return result[0]; }
相关推荐
python python_leetcode题解之132_Palindrome_Partitioning_II
javascript js_leetcode题解之132-palindrome-partitioning-ii.js
python python_leetcode题解之131_Palindrome_Partitioning
javascript js_leetcode题解之131-palindrome-partitioning.js
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
1. **Palindrome Partitioning (mine).cpp** - 这个文件是关于LeetCode的第131题“回文分割”。该问题要求将一个字符串分割成多个回文子串。解冑通常涉及深度优先搜索或动态规划,寻找所有可能的分割方案并检查是否...
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
gas station leetcode 在牛客网上的在线编程...palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
Palindrome_Partitioning DP,避免递归调用,利用数组储存已算出来的数值,由后向前逐渐增加字符串处理 Palindrome_Partitioning_2 同上 Sum_Root_to_Leaf_Numbers DFS Surrounded_Regions 由四周‘O’开始向内检索...
分割回文串(Palindrome Partitioning)**:这是一个关于字符串处理的题目,要求将一个字符串分割成若干个回文子串。主要涉及的算法是深度优先搜索(DFS),通过递归的方式检查所有可能的分割方案,判断是否都是回文。 ...
3. 题目131 - "Palindrome Partitioning" 这是一道回文子串分割问题,要求将一个字符串分割成多个回文子串。常见的解法是动态规划,创建一个二维数组来存储子问题的最优解。在Java中,可以使用StringBuilder和...
对于更高级的题目,可能会涉及图论或动态规划,比如`0131_palindrome_partitioning.py`可能涉及回文子串分割,这通常会用到动态规划来避免重复计算。 在PythonAlgo项目中,每个问题的解决方案都提供了清晰的思路和...