- 浏览: 172597 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
给定一个字符串s,用最少的次数将它拆分成多个回文子串。我们用动态规划来解决。首先我们用一个二维的布尔数组isPalin[][]记录当前子串是否是回文串,例如isPalin[i][j] = true,就代表了字符串中从字符i到字符j是回文子串。(当s.charAt(i) == s.charAt(j)并且i + 1 >= j - 1的时候,也就是对应了’aa‘和’a?a‘这两种情况,此时肯定为回文串)。用数组dp[]来记录每个阶段的最小值,如果检测到从第一个字符到当前字符为回文子串,那么dp[j] = 0, 因为不需要拆分所以为0; 如果从字符i开始到当前字符为回文子串并且i > 0,此时dp[j] = dp[i - 1] + 1。实现代码如下:
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.
给定一个字符串s,用最少的次数将它拆分成多个回文子串。我们用动态规划来解决。首先我们用一个二维的布尔数组isPalin[][]记录当前子串是否是回文串,例如isPalin[i][j] = true,就代表了字符串中从字符i到字符j是回文子串。(当s.charAt(i) == s.charAt(j)并且i + 1 >= j - 1的时候,也就是对应了’aa‘和’a?a‘这两种情况,此时肯定为回文串)。用数组dp[]来记录每个阶段的最小值,如果检测到从第一个字符到当前字符为回文子串,那么dp[j] = 0, 因为不需要拆分所以为0; 如果从字符i开始到当前字符为回文子串并且i > 0,此时dp[j] = dp[i - 1] + 1。实现代码如下:
public class Solution { public int minCut(String s) { if(s == null) return 0; boolean[][] isPalin = new boolean[s.length()][s.length()]; int[] dp = new int[s.length()]; for(int i = 0; i < dp.length; i++) { int min = i; for(int j = 0; j <= i; j++) { if(s.charAt(j) == s.charAt(i) && (j + 1 >= i - 1 || isPalin[j + 1][i - 1])) { isPalin[j][i] = true; min = (j == 0) ? 0 : Math.min(min, dp[j - 1] + 1); } } dp[i] = min; } return dp[s.length() - 1]; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 446Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 425Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 857Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 549Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
Palindrome Partitioning II Maximal Rectangle Best Time to Buy and Sell Stock III Best Time to Buy and Sell Stock IV Best Time to Buy and Sell Stock with Cooldown Interleaving String Scramble String ...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
北大POJ1159-Palindrome 解题报告+AC代码
C++实现的Palindrome,回文 C++实现的Palindrome,回文
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
各位帮帮忙吧
Palindrome Sub-Array,Problem Description A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-...
回文分区 动态规划 | 第 17 组(回文分区)( )
palindrome22.in
回文数Java
北大POJ1159-Palindrome
LeetCode Palindrome Number解决方案
palindrome_prime.c
Palindrome.py
检查字符串是否为palindrome, 从前后分别检查,并计算出相同或不同的数量。
GET /java-palindrome-example/palindrome/ 解析提供的字符串,并找到其中包含的最大回文。 在此情况下,也可以将type的可选查询参数设置为slow在这种情况下,服务将使用慢得多的递归算法。 例子 GET /java-...
安装要安装bencreating_palindrome ,请将此行添加到应用程序的Gemfile : gem 'bencreating_palindrome'然后安装如下: $ bundle install或者直接使用gem安装它: $ gem install bencreating_palindrome用法...
palindrome number in c
palindrome(STACK,QUEUE).cpp