Palindrome Partitioning

题目原型：

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

基本思路：

 思路一：递归

	public ArrayList<ArrayList<String>> partition(String s)
	{
		ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
		ArrayList<String> tmp = new ArrayList<String>();
		
		getRs(list, tmp, s);
		
		return list;
	}
	
	public void getRs(ArrayList<ArrayList<String>> list,ArrayList<String> tmp,String s)
	{
		if(s.length()==0||s==null)
		{
			list.add(new ArrayList<String>(tmp));
			return;
		}
		else
		{
			for(int i = 1;i<=s.length();i++)
			{
				if(isPalindrome(s.substring(0, i)))
				{
					tmp.add(s.substring(0, i));
					getRs(list, tmp, s.substring(i));
					tmp.remove(tmp.size()-1);
				}
			}
		}
	}
	//判断一个字符串是否是回文
	public boolean isPalindrome(String s)
	{
		if(s==null||s.length()==0)
			return true;
		
		for(int i = 0,j = s.length()-1;i<j;i++,j--)
		{
			if(s.charAt(i)!=s.charAt(j))
				return false;
		}
		return true;
	}

思路二：

利用一个table表存放某个字符到另一个字符之间是否是回文。例如要判断i和j之间的字符串是否是回文，那么我们就要判断s[i]?=s[j]和i+1与j-1之间是字符串是否是回文。

	public ArrayList<ArrayList<String>> partition(String s)
	{
		//创建一个table表
		boolean[][] table = new boolean[s.length()][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);
		
		ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
		ArrayList<String> tmp = new ArrayList<String>();
		
		getRs(list, tmp, s, table, 0);
		
		return list;
	}
	
	public void getRs(ArrayList<ArrayList<String>> list,ArrayList<String> tmp,String s,boolean[][] table,int start)
	{
		if(start == s.length())
		{
			list.add(new ArrayList<String>(tmp));
			return;
		}
		else
		{
			for(int i = 1;i<=s.length()-start;i++)
			{
				if(table[start][start+i-1])
				{
					tmp.add(s.substring(start, start+i));
					getRs(list, tmp, s,table,start+i);
					tmp.remove(tmp.size()-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,布布扣,bubuko.com

Palindrome Partitioning

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