[leetcode]132. Palindrome Partitioning II

Airy 发布于2019-08-14 16:54 / 2230人阅读

摘要：用表示当前位置最少需要切几次使每个部分都是回文。表示到这部分是回文。如果是回文，则不需重复该部分的搜索。使用的好处就是可以的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。

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.

用cuts[i]表示当前位置最少需要切几次使每个部分都是回文。如果s(j,i)这部分是回文，就有cuts[i] = cuts[j-1] + 1。
现在我们需要做的就是对于已经搜索并确定的回文部分，用一个二维数组来表示。matrix[j] [i]表示j到i这部分是回文。
如果s.charAt(i) == s.charAt(j) && isPalindrome[j+1] [i-1]是回文，则不需重复该部分的搜索。isPalindrome[j] [i]也是回文。

以"abcccba"为例：
i不断向后扫描， j从头开始知道i(包含i).
i=3即第二个c那里，j走到2, c[i] == c[j] == "c" && i - j = 1 < 2，填表，求最值。
i=4即第三个c那里，j走到2, c[i] == c[j] == "c" && isPalindrome(2+1,4-1), 填表，求最值。
i=5即第二个b那里，j走到1, c[i] == c[j] == "b" && isPalindrome(1+1,5-1)即“ccc“，填表，求最值。
使用isPalindrome的好处就是可以O(1)的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。

public class Solution {
    public int minCut(String s) {
        char[] c = s.toCharArray();
        int n = s.length();
        int[] cuts = new int[n]; // cuts[i] = cut[j-1] + 1 if [j,i] is panlindrome
        boolean[][] isPalindrome = new boolean[n][n]; // isPalindrome[j][i] means  [j,i] is panlidrome
        
        for(int i=0; i

idc机房托管云服务器 palindrome Partitioning -partitioning 132邮箱

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66310.html

leetcode132. Palindrome Partitioning II

摘要：题目要求现在有一个字符串，将分割为多个子字符串从而保证每个子字符串都是回数。我们只需要找到所有可以构成回数的并且得出最小值即可。即将字符作为，将字符所在的下标列表作为。再采用上面所说的方法，利用中间结果得出最小分割次数。题目要求 Given a string s, partition s such that every substring of the partition is a ...

jeyhan 2019-08-15 14:27 评论0 收藏0
[LintCode] Palindrome Partitioning II

摘要：假设我们从后向前，分析到第位，开始判断，若为，说明从第位向前到第位的子串是一个回文串，则就等于第位的结果加。然后让继续增大，判断第位到最后一位的范围内，有没有更长的回文串，更长的回文串意味着存在更小的，用新的来替换。 Problem Given a string s, cut s into some substrings such that every substring is a p...

funnyZhang 2019-08-14 15:30 评论0 收藏0
[Leetcode] Palindrome Partitioning 回文分割

摘要：深度优先搜素复杂度时间空间思路因为我们要返回所有可能的分割组合，我们必须要检查所有的可能性，一般来说这就要使用，由于要返回路径，仍然是典型的做法递归时加入一个临时列表，先加入元素，搜索完再去掉该元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...

leanote 2019-08-14 12:32 评论0 收藏0
[LeetCode] 267. Palindrome Permutation II

Problem Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. Example Given s = aabb, return [abba,baa...

huashiou 2019-08-16 12:40 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0