[LintCode] Palindrome Partitioning II

funnyZhang 發布于2019-08-14 15:30 / 2592人閱讀

摘要：假設我們從后向前，分析到第位，開始判斷，若為，說明從第位向前到第位的子串是一個回文串，則就等于第位的結果加。然后讓繼續增大，判斷第位到最后一位的范圍內，有沒有更長的回文串，更長的回文串意味著存在更小的，用新的來替換。

Problem

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example

Given s = "aab",

Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

Note

Palindrome Partitioning I是DFS的做法，II是DP的做法。
本題的思路是：建立boolean二維數組dp[i][j]，存放字符串s從第i到第j位是否為回文的布爾值；同時建立整型數組min[i]，存放從最后一位到第i位都是回文串的最小切割次數。然后從字符串s的最后一個字符開始，向前進行分析。
舉個例子。假設我們從后向前，分析到第i位，開始判斷dp[i][j]，若為true，說明從第j位向前到第i位的子串是一個回文串，則min[i]就等于第j位的結果min[j]加1。然后讓j繼續增大，判斷第i位到最后一位的范圍內，有沒有更長的回文串，更長的回文串意味著存在更小的min[j]，用新的min[j]+1來替換min[i]。

Solution

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int[] min = new int[n];
        for (int i = n-1; i >= 0; i--) {
            min[i] = n-i-1;
            for (int j = i; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (dp[i+1][j-1] || j-i <= 1);
                if (dp[i][j]) min[i] = Math.min(min[i], j+1 < n ? min[j+1]+1 : 0);
            }
        }
        return min[0];
    }
};

云服務器 GPU云服務器 palindrome Partitioning -partitioning LintCode

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65809.html

[LintCode] Palindrome Partitioning

Problem Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example Given s = aab, return: [ [aa,b], [a,a,b...

NicolasHe 2019-08-14 15:11 評論0 收藏0
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
[leetcode]132. Palindrome Partitioning II

摘要：用表示當前位置最少需要切幾次使每個部分都是回文。表示到這部分是回文。如果是回文，則不需重復該部分的搜索。使用的好處就是可以的時間，也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...

Airy 2019-08-14 16:54 評論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
131. Palindrome Partitioning and 140. Word Break I

摘要：找到開頭的某個進行切割。剩下的部分就是相同的子問題。記憶化搜索，可以減少重復部分的操作，直接得到后的結果。得到的結果和這個單詞組合在一起得到結果。 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome...

stonezhu 2019-08-14 17:58 評論0 收藏0