`
standalone
  • 浏览: 613047 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

[leetcode] Palindrome Partitioning II

 
阅读更多
http://leetcode.com/onlinejudge#question_132

Question:

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.

Solution:

DP problem, but my first try failed due to time limitation. The root cause is you should try to optimize the Palindrome calculation. The solution below borrows from others idea found from the discussion page. Thanks to the author.

public class Solution {
    public int minCut(String s) {
        int leng = s.length();
        if(leng == 0 || leng == 1) return 0;
        boolean[][] isPal = new boolean[leng][leng];

        int[] dp = new int[leng]; 
        for (int i = 0; i < leng; i++) {
            dp[i] = leng - 1 - i;
        }

        for (int i = leng - 1; i >= 0; --i) {
            for (int j = i; j < leng; ++j) {
                if (s.charAt(i) == s.charAt(j) && (j <= i + 2 || (i + 1 < leng && j - 1 >= 0 && isPal[i + 1][j - 1]))) {
                    isPal[i][j] = true;
                    if(j+1 < leng){
                        dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
                    }else {
                        dp[i] = 0;
                    }
                }
            }
        }

        return dp[0];
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution s = new Solution();
        int cut = s.minCut("abccdcba");
        System.out.println(cut);
    }

}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics