132. Palindrome Partitioning II

Link

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.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution

設計一個dp[]，每個dp[i] 表示 substring(0...i)裡面的最小cut數。

根據每個點mid向兩側(透過start, end pointers)進行expand看看是否可以成為palindrome， 假設可以形成回文，那就表示dp[end]其中一個可能為 1 + dp[start-1]，其中1表示s[start....end]，因為它可以當成一個回文。 考慮egde case， start == 0，表示s[0....end]整串都是回文，那麼dp[end]就是0

若start != 0 : dp[end] = Math.min(dp[end], dp[start-1] + 1);

並考慮expand mid時，奇數長跟偶數長回文長度的可能

   public int minCut(String s) {
        int len = s.length();
        int[] dp = IntStream.range(0, len).toArray();
        
        for(int mid = 1; mid < len ; mid++ ){
            //expand from mid, assume it's length is odd
            for(int start = mid, end = mid; start >= 0 && end < len && s.charAt(start) == s.charAt(end);
               start--, end++){
                //minCutOf[0.....start-1] + 1(substring(start,end) would be one palindrome) -> 
                int newCutAtEnd = start == 0 ? 0 : dp[start-1] + 1;
                dp[end] = Math.min(dp[end], newCutAtEnd);
            }
            //expand from mid assume it's length is even
            for(int start = mid-1, end = mid; start>=0 && end < len &&s.charAt(start) == s.charAt(end);
               start--, end++){
                int newCutAtEnd = start == 0 ? 0 : dp[start-1] + 1;
                dp[end] = Math.min(dp[end], newCutAtEnd);
                
            }
        }
        return dp[len-1];

    }