首页 > 代码库 > [leetcode]Palindrome Partitioning II
[leetcode]Palindrome Partitioning II
Palindrome Partitioning II
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",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.
算法思路：
思路1：dfs，求出所有的可能截断情况，再计算其中最小的。不用试，肯定超时。例如"aaaa....aaaaaaaa"
思路2：dp。发现了回文串的dp方法还是比较好认知的。
dp[i][j]代表字符串s.substring( i , j )是否是回文的。
初始化状态dp[i][i] = true( 0 <= i < s.length )
dp[i][j] = true有两种情况：
1）s.charAt(i) == s.charAt(j) ，且j = i + 1
2）s.charAt(i) == s.charAt(j) ，且dp[i + 1][ j - 1] = true（因此要数组要从下往上，从左往右的迭代）
cuts[i]表示s.substring(i)的最小切分数，初始化是length - i - 1;
当dp[i][j] == true时，则cuts[i] = min(cuts[i],cuts[j + 1])( j = s.length - 1)或者cuts[i] = min(cuts[i],cuts[j + 1] + 1)
这个应该不难理解
代码如下：
1 public class Solution { 2 public int minCut(String s) { 3 if(s == null || s.length() < 2) return 0; 4 int length = s.length(); 5 boolean[][] isPal = new boolean[length][length]; 6 int[] cuts = new int[length + 1]; 7 for(int i = length - 1; i >= 0; i--){ 8 cuts[i] = length - i - 1; 9 for(int j = i ; j < length; j++){10 if(s.charAt(i) == s.charAt(j) && (j - i < 2 || isPal[i + 1][j - 1])){11 isPal[i][j] = true;12 if(j == length - 1){13 cuts[i] = Math.min(cuts[i], cuts[j + 1]);14 }else{15 cuts[i] = Math.min(cuts[i], cuts[j + 1] + 1);16 }17 }18 }19 }20 return cuts[0] ; 21 }22 }