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.

基本思路：

题目的意思就是在上一题的基础上找出切分次数最少的组合，即尽可能让回文字符串更长。那么我们同样生成table表用来存储i到j之间的字符串是否是回文；然后遍历字符串来更新最小的切分次数。

	public int minCut(String s)
	{
		if(s==null||s.length()==0)
			return 0;
		//创建一个table表
		boolean[][] table = new boolean[s.length()][s.length()];
		
		int[] rs = new int[s.length()];
		
		for(int i = 0;i<table.length;i++)
		{
			for(int j = 0;j<table.length;j++)
				table[i][j] = true;
		}
		//产生table表
		genTable(table,s);
		if(table[0][table.length-1])
			return 0;
		
		for(int i = 1;i<s.length();i++)
		{
			if(table[0][i])
			{
				rs[i] = 0;
				continue;
			}
			rs[i] = rs[i-1]+1;//不要s[i]参与
			//要s[i]参与
			for(int j = 0;j<i;j++)
			{
				if(table[j][i])
					rs[i] = Math.min(rs[i],rs[j-1]+1);
			}
		}
		
		return rs[rs.length-1];
	}
	
	
	//产生table表
	public void genTable(boolean[][] table,String s)
	{
		//根据间距从小到大来遍历
		for(int dis = 1;dis<table.length;dis++)
		{
			for(int i = 0,j = i+dis;j<table.length;i++,j++)
			{
				table[i][j] = (table[i+1][j-1]&&(s.charAt(i)==s.charAt(j)));
			}
		}
	}

Palindrome Partitioning II,布布扣,bubuko.com

Palindrome Partitioning II

原文：http://blog.csdn.net/cow__sky/article/details/21736799