[leetcode]132. Palindrome Partitioning II

Airy 發布于2019-08-14 16:54 / 2356人閱讀

摘要：用表示當前位置最少需要切幾次使每個部分都是回文。表示到這部分是回文。如果是回文，則不需重復該部分的搜索。使用的好處就是可以的時間，也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。

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

云服務器 GPU云服務器 palindrome Partitioning -partitioning 132郵箱

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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