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.A:
Dynamic programming. (quite similar to Matrix - chain problem)
public class PalindromePartitioningII { public int minCut(String s) { int n = s.length(); if (n == 0) return 0; // use an matrix to record if a subString of s is palindrome. boolean[][] isPalindromeArray = new boolean[n][n]; // record only i<=j buildPalindromeArray(s, isPalindromeArray); // for each just added s[i], record which minimum cut for s[0....i], // and its number int[] minCutNum = new int[n + 1]; // minCutNum[i] means the after the // ith position minCutNum[0] = -1; // add each char from the front to end for (int j = 1; j <= n; j++) { minCutNum[j] = minCutNum[j - 1] + 1; // now we combine the suffix part, with s.charAt(i) for (int i = j - 1; i >= 1; i--) { if (isPalindromeArray[i - 1][j - 1]) {// if substring s[i-1, ... // ,j-1] is palindrome minCutNum[j] = Math.min(minCutNum[j], 1 + minCutNum[i - 1]); } } } return minCutNum[n]; } private void buildPalindromeArray(String s, boolean[][] isPalindromeArray) { // following matrixly calling method is too time consuming, because of // the repeated calling the function // Solution : using the dynamic programming philosophy. // using the small edge to build the long edge // for (int i = 0; i < n; i++) { // for (int j = i + 1; j < n; j++) { // isPalindromeArray[i][j] = isPalindrome(s.substring(i, j + 1)); // } // } for (boolean[] row : isPalindromeArray) Arrays.fill(row, true); // initialize the row as TRUE, // for substring length of i=j, means one character, it is already set // to zeros for (int len = 1; len < s.length(); len++) { // here , length = j - i int j; // j is the end point of a substring for (int i = 0; i < s.length() - len; i++) { j = i + len; isPalindromeArray[i][j] = (s.charAt(i) == s.charAt(j) && isPalindromeArray[i + 1][j - 1]); } } } }
上面这个想法,还是挺SB的,毕竟要n^2的空间。 到底是自己做的第二道leetcode 的题目啊。
新想法如下,有一个链表数组: 对每个位置, 有该位置可以与previous position 构成 palindrome 的位置的信息
另外加一个minCut[] 来记录对每一个地址,其number of minimum cut.
public class Solution { public int minCut(String s) { int n = s.length(); int[] minCut = new int[ n ]; List<List<Integer>> paliPos = new ArrayList<>(); for(int i =0;i<n;i++){ List<Integer> al = new ArrayList<>(); al.add(i); paliPos.add(al); } for(int i=1;i<n;i++){ char ch = s.charAt(i); minCut[i] = 1 + minCut[i-1]; if(ch == s.charAt(i-1) ){ // direct match with the left minCut[i] = Math.min(minCut[i], (i==1) ? 0: 1+minCut[i-2] ); paliPos.get(i).add(i-1); } List<Integer> leftPosList = paliPos.get(i-1); for(int pos : leftPosList){ if(pos>0 && s.charAt(pos-1) == ch){ paliPos.get(i).add(pos-1); minCut[i] = Math.min( minCut[i], pos ==1 ? 0 : 1 + minCut[pos-2] ); } } } return minCut[n-1]; } }
-----------------------------思路1 的重新实现 (第二遍做的)--------------------------------------
public class Solution { public int minCut(String s) { if(s.length()<=1 ) return 0; // build a 2D array, indicating whether each [i,j] position makes an palindrome int n = s.length(); boolean[][] isPalin = new boolean[n][n]; //build the whole set for(int j =0;j<n;j++){ isPalin[j][j] = true; //set [i][i] == true for(int i = j-1; i>=0; i--){ isPalin[i][j] = s.charAt(i)==s.charAt(j) &&( isPalin[i+1][j-1] || i+1 == j); } } // build a minCut from begining to end int[] minCut = new int[n]; for(int i =1;i<n;i++){ minCut[i] = minCut[i-1] +1; //check all its previous mathing for(int j = 0;j<i;j++){ if(isPalin[j][i] == true){ if(j ==0){ minCut[i] = 0; }else{ // coz we gonna use j-1 as index minCut[i] = Math.min(minCut[j-1] +1,minCut[i]); } } } } return minCut[n-1]; } }
(呵呵,看来,做题还是有进步的。╮(╯▽╰)╭ 刚开始,光晕去了)
Mistakes:
1: when input string is too large, still declaring the isPalindromeArray[n][n] is too time comsuming
2: when building MatchPos ArrayList, I forget the case that the char at i_th position could be matched directly with one single ahead.
例如: aab, 得到的list 应该是[0][0,1][0,1,2]
因此要测试, i 和i-1的匹配( 在 如果两个紧挨着, 就无法分出preMatch来了
3: 2遍: 在建立2D isPalindrome array的时候,应该从 没加入一个字符, 基于 其前面所有的match 的情况已经计算出来。
因此, for (j =0, j< n;j++)
for ( i =j-1;i >=0;i--)
4: 2遍; 在基于之前的计算的时候, 要考虑,前面的是否存在, 亦即 i ==j-1的时候。
Learned:
TPTP 等分析代码运行时间的插件都不能用。 还是用最简单的 打印出各自运行的时间就行。
long beginTime = System.nanoTime(); System.out.println((System.nanoTime() - beginTime)/10000); beginTime = System.nanoTime();然后,每次upddate beginTime, 对比就行。 System.currentTimeMillis vs System.nanoTime 都是返回long类型,但是区别呢???
2: Arrays.fill() 函数,只能对一维数组填充。 多维的,要自己去一维得填 (可以利用Arrays.fill() 函数)
2: 如果是在eclipse中运行,需要import 一些库,例如import java.util.*;
别人的解法:(但基本上,还是自己的最好,不用判断回文的函数。)
有一个是利用DFS回溯的。调用O(n^2) 次dfs, 貌似不太好。
-----------------------------利用递归调用,每次取后面的----------
No comments:
Post a Comment