最优解问题,直观想到动态规划来解,那么首先是找到状态方程
假设f[i]代表0-i的数组长度内的最小切分,那么有以下转移条件
1. 0-i 整体为回文,那么f[i]=0
2. 0-i 不是回文, 那么必然存在0<j<=i 是的j-i 是回文, 那么对这个集合求最小值f[i]=min{f[j-1]+1},0<j<=i
注意红色部分初始化代码的技巧,普通的双层循环为导致超时
第一层循环定义了i和j的间距,后一次循环可以使用前一层循环的结果, 时间复杂度小于O(N*N),更重要的减小回文判断的复杂度以及次数
public class Solution {
public int minCut(String s) {
boolean[][] p = new boolean[s.length()][s.length()];
char[] c = s.toCharArray();
for (int i = 0; i < c.length; i++) {
p[i][i] = true;
}
for (int k = 1; k < c.length; k++) {
for (int i = 0; i + k < c.length; i++) {
int j = i + k;
p[i][j] = c[i] == c[j] && (i + 1 < j - 1 && p[i + 1][j - 1] || i + 1 >= j - 1);
}
}
int[] f = new int[s.length()];
for(int i=1; i<f.length; i++){
f[i] = i;
}
for(int i=1; i<s.length(); i++){
if(p[0][i]){
f[i]=0;
continue;
}
for(int j=0; j<=i; j++){
if(p[j][i] && (f[j-1]+1)<f[i]){
f[i]=f[j-1]+1;
}
}
}
return f[s.length()-1];
}
}
相关推荐
Article-Views-II-LeetCode.png 平均工资-部门-VS-公司-LeetCode.png 平均销售价格-LeetCode.png 每台机器平均处理时间 LeetCode.png Bank-Account-Summary-II-LeetCode.png Bank-Account-Summary-LeetCode.png 大国...
leetcode 答案Leetcode-Java - 符合条件(Hacktoberfest) JAVA 中的 Leetcode 答案
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
leetcode 跳跃 LeetCode-Java 缺失的第一个正数 接雨水 跳跃游戏 II
LeetCode-Java 说明 leetcode练习,坚持每天一道,目前已完成275道 解题语言是Java 每道题都是可编译运行的 每道题有自己的方法和他人优秀解法 每道题会尽量分析一下解题步骤和复杂度 欢迎star、fork、交流,一起...
leetcode题库 leetcode-java 用Java实现leetcode题库
leetcode-java LeetCode Java Solution 题目 : : : : more : : : : : : more : : : 题解 recursion 104题解 解法:递归 复杂度:O(n)、O(h) class Solution { public int maxDepth(TreeNode root) { //...
leetcode 答案 leetcode-java 记录Leetcode之旅。 内容包括最终的答案,思考和截图等。 一道题可能会在一段时间之内复习,所以会有不同的答案。
java lru leetcode leetcode-algorithms-java leetcode 算法笔记-java
分类LeetCode-Java-接受 这是 Leetcode 问题的 Java 解决方案。 细节 标题和答案格式 /* * 17. Letter Combinations of a Phone Number * Target: Given a string containing digits from 2-9 inclusive, return all...
LeetCode Palindrome Number解决方案
本仓库内包含了java实现的leetcode解法,代码规范,可读性良好,其中的解法思想并不受语言限制。 BFS(Breath First Search) bfs能解决什么样的问题 图遍历中是否可达、最短路径等等。 普通bfs解题框架 一个boolean[]...
java lru leetcode LeetCode-Tag-Java 解决方案 LeetCode 的解决方案 指数
awesome-java-leetcode 我如今是一名 Android Developer,大学的我曾是一名 ACMer,我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的,为了不让数据结构和算法淡出我的记忆,所以我打算重拾 LeetCode ...
leetcode 分配Leetcode 回文素数禁食解 几个具有 0ms 执行时间的解决方案和 leetcode 问题的基准。 基准测试结果 Benchmark_primePalindrome/letientai299-12 20000 95646 ns/op 1008 B/op 29 allocs/op ...
java lru leetcode Java 中的 Leetcode 解决方案 算法 # 问题 解决方案 1 [Java](/Java/001 二和.java) 2 [Java](/Java/002 加两个数.java) 3 [Java](/Java/003 无重复字符最长子串.java) 4 [Java](/Java/004 两个...
解压Leetcode-Solution-With-Java 用 Java 8 解决 Leetcode 问题 编号 问题 解决方案 困难 01 简单的 02 中等的 03 无重复字符的最长子串 中等的 04 两个有序数组的中位数 难的 653 二和 IV - 输入是 BST 简单的 ...
leetcode 不会 Leetcode Solutions in Java Linked List Linked List Cycle Given a linked list, determine if it has a cycle in it. public static boolean hasCycle(ListNode head) 快慢指针法,块指针从head....
leetcode-java leetcode题库Java解决方案 这是一个IntelliJ IDEA项目,请安装IntelliJ IDEA Test.java是测试入口,如要测试请修改Q后面的数字,比如这是测试第23题 public static void main(String[] args) { ...
这个库文件中的所有代码均由java语言编写,所有题目皆来自于LeetCode官网 关于这些代码,有以下几点说明: 1.所有代码均为原创,可随意转载、使用、修改; 2.代码以简洁明了为原则,逻辑清晰; 3.欢迎大家随时交流,...