資訊專欄INFORMATION COLUMN
摘要：假設(shè)我們從后向前，分析到第位，開(kāi)始判斷，若為，說(shuō)明從第位向前到第位的子串是一個(gè)回文串，則就等于第位的結(jié)果加。然后讓繼續(xù)增大，判斷第位到最后一位的范圍內(nèi)，有沒(méi)有更長(zhǎng)的回文串，更長(zhǎng)的回文串意味著存在更小的，用新的來(lái)替換。
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.
ExampleGiven s = "aab",
Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.
NotePalindrome Partitioning I是DFS的做法，II是DP的做法。
本題的思路是：建立boolean二維數(shù)組dp[i][j]，存放字符串s從第i到第j位是否為回文的布爾值；同時(shí)建立整型數(shù)組min[i]，存放從最后一位到第i位都是回文串的最小切割次數(shù)。然后從字符串s的最后一個(gè)字符開(kāi)始，向前進(jìn)行分析。
舉個(gè)例子。假設(shè)我們從后向前，分析到第i位，開(kāi)始判斷dp[i][j]，若為true，說(shuō)明從第j位向前到第i位的子串是一個(gè)回文串，則min[i]就等于第j位的結(jié)果min[j]加1。然后讓j繼續(xù)增大，判斷第i位到最后一位的范圍內(nèi)，有沒(méi)有更長(zhǎng)的回文串，更長(zhǎng)的回文串意味著存在更小的min[j]，用新的min[j]+1來(lái)替換min[i]。
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];
}
};
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65809.html
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...
摘要：題目要求現(xiàn)在有一個(gè)字符串，將分割為多個(gè)子字符串從而保證每個(gè)子字符串都是回?cái)?shù)。我們只需要找到所有可以構(gòu)成回?cái)?shù)的并且得出最小值即可。即將字符作為，將字符所在的下標(biāo)列表作為。再采用上面所說(shuō)的方法，利用中間結(jié)果得出最小分割次數(shù)。 題目要求 Given a string s, partition s such that every substring of the partition is a ...
摘要：用表示當(dāng)前位置最少需要切幾次使每個(gè)部分都是回文。表示到這部分是回文。如果是回文，則不需重復(fù)該部分的搜索。使用的好處就是可以的時(shí)間，也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...
摘要：深度優(yōu)先搜素復(fù)雜度時(shí)間空間思路因?yàn)槲覀円祷厮锌赡艿姆指罱M合，我們必須要檢查所有的可能性，一般來(lái)說(shuō)這就要使用，由于要返回路徑，仍然是典型的做法遞歸時(shí)加入一個(gè)臨時(shí)列表，先加入元素，搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...
摘要：找到開(kāi)頭的某個(gè)進(jìn)行切割。剩下的部分就是相同的子問(wèn)題。記憶化搜索，可以減少重復(fù)部分的操作，直接得到后的結(jié)果。得到的結(jié)果和這個(gè)單詞組合在一起得到結(jié)果。 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome...
閱讀 1992·2021-11-24 09:39
閱讀 2161·2021-09-22 15:50
閱讀 2084·2021-09-22 14:57
閱讀 738·2021-07-28 00:13
閱讀 1101·2019-08-30 15:54
閱讀 2385·2019-08-30 15:52
閱讀 2715·2019-08-30 13:07
閱讀 3815·2019-08-30 11:27
