Java-Palindrome Partitioning

浏览数：20 / 时间：2015年06月08日

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"]
  ]

将给定字符串进行分解使每一个分部都是回文结构要求给出所有可能的组合

典型的回溯法求解每次从第index位开始拆分 i=(index,s.length()-1) 若index-i位满足回文结构则从第i+1位继续递归需要注意的是结束条件可以是index=s.length()即所有位都拆分完毕代码如下：

public class Solution {
 
    public  List<List<String>> partition(String s) {
		List<List<String>> res=new ArrayList<List<String>>();
		List<String>  tmp=new ArrayList<String>();
		part(res, s, tmp, 0);
		return res;
    }
	public   void part( List<List<String>> res,String s,List<String>  tmp,int index){
		if(index==s.length()){
			res.add(tmp);
			return;
		}
		for(int i=index;i<s.length();i++){
			if(isPalindrome(s, index, i)){
				List<String>  ntmp=new ArrayList<String>();
				ntmp.addAll(tmp);
				ntmp.add(s.substring(index,i+1));
				part(res, s, ntmp, i+1);
			}
		}
	}
	public  boolean isPalindrome(String s,int start,int end){
		for(int i=0;i<(end-start+1)/2;i++){
			if(s.charAt(i+start)!=s.charAt(end-i)){
				return false;
			}
		}
		return true;
	}
    
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java-Palindrome Partitioning