http://leetcode.com/onlinejudge#question_132
Question:
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.
Solution:
DP problem, but my first try failed due to time limitation. The root cause is you should try to optimize the Palindrome calculation. The solution below borrows from others idea found from the discussion page. Thanks to the author.
public class Solution {
public int minCut(String s) {
int leng = s.length();
if(leng == 0 || leng == 1) return 0;
boolean[][] isPal = new boolean[leng][leng];
int[] dp = new int[leng];
for (int i = 0; i < leng; i++) {
dp[i] = leng - 1 - i;
}
for (int i = leng - 1; i >= 0; --i) {
for (int j = i; j < leng; ++j) {
if (s.charAt(i) == s.charAt(j) && (j <= i + 2 || (i + 1 < leng && j - 1 >= 0 && isPal[i + 1][j - 1]))) {
isPal[i][j] = true;
if(j+1 < leng){
dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
}else {
dp[i] = 0;
}
}
}
}
return dp[0];
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution s = new Solution();
int cut = s.minCut("abccdcba");
System.out.println(cut);
}
}
分享到:
相关推荐
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项目中,每个问题的解决方案都提供了清晰的思路和...