首页 > ACM题库 > LeetCode > Palindrome Partitioning II-动态规划
2014
10-06

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",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

分析

此题可以用动态规划求解。isPal[i][j]表示字符串s的子串s[i...j]是否为回文串,cut[j]表示子串s[0...j]所需要的最小分割数。

代码如下:

public class PalindromePartitioning {
	public int minCut(String s) {
		int n = s.length();
		boolean isPal[][] = new boolean[n][n];
		int cut[] = new int[n];
		for (int j = 0; j < n; j++) {
			cut[j] = j;
			for (int i = 0; i <= j; i++) {

				//如果子串 s[i...j]是回文串
				if (s.charAt(i) == s.charAt(j)
						&& (j - i <= 1 || isPal[i + 1][j - 1])) {
					isPal[i][j] = true;
					if (i > 0)
						cut[j] = Math.min(cut[j], cut[i - 1] + 1);
					else
						cut[j] = 0; //如果 s[0...j]是回文串,则说明不需要切割
				}
			}
		}
		return cut[n - 1];
	}

	public static void main(String[] args) {
		String s = "aabbcaac";
		PalindromePartitioning2 pp = new PalindromePartitioning2();
		System.out.println(pp.minCut(s));
	}
}

  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish