新博文地址:
[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]; }
相关推荐
LeetCode Palindrome Number解决方案
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode卡leetcode_practices_learncard_recursionii 我的 leetcode 递归练习 ii 学习卡在 100% 完成 :) 我的 Java8 备忘单:
462 | [Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/) | [C++](./C++/minimum-moves-to-equal-array-elements-ii.cpp) [Python](./Python/...
Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating ...
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中删除重复项 代码: Leetcode\RemoveDuplicates\RemoveDuplicates.cs 问题: 买卖股票的最佳时机 II 代码: Leetcode\MaxProfit\MaxProfit.cs ...
vs code LeetCode 插件
vscode安装leetcode 回文 这是分支、循环和其他基本 C# 概念的练习,以构建工作控制台应用程序。5/5/2020 由 Nitun Dtta 和 Matt Stroud 制作 描述 这是一个控制台应用程序,允许用户提供任何单词、短语、数字或其他...
leetcode中文版
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode刷题, 直接用leetcode的分类方式.