本文共 1257 字，大约阅读时间需要 4 分钟。

LeetCode刷题：132. 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.

Example:

Input: "aab"

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"

算法设计

/*	 * 基本思想是使用两个DP数组：	 * 使用isPalindrome[i，j]来记录 s[i, j]是否为回文串，	 * 以及num[i]来记录对于s[0，i]的最小划分。	 * 这里s[i，j]代表的含义是：s.substring（i，j+1）。	 * 遍历访问数组以计算：num 和 ispalindrome。	 * num[s.length（）-1]是我们想要的结果。	 * 注意，如果s[0，i]是回文串，那么num[i]等于零，因为我们不需要划分它来得到回文序列。	 * */		public int minCut(String s) {	    char str[] = s.toCharArray();	    boolean isPalindrome[][] = new boolean[s.length()][s.length()];	    int num[] = new int[s.length()];	    for(int i = 0; i < s.length(); i++) {	        int min = Integer.MAX_VALUE;	        for(int j = 0; j <= i; j++) {	            if( str[i] == str[j] && (j + 1 >= i || isPalindrome[j + 1][i - 1]) ){	                isPalindrome[j][i] = true;	                min = j == 0 ? 0 : Math.min(min, num[j - 1] + 1);	            }	        }	        num[i] = min;	    }	    return num[s.length() - 1];	}

Accepted~

转载地址：http://wntdi.baihongyu.com/