Palindrome Partitioning (Java)

LeetCode

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

Solution: DFS, Recursion

declare start point st, make it move from 0-> s.length(), for each st, check every substring generated by st and i, st+1<=i<=s.length(), if the substring is a palindrome then put it into ArrayList<String>  partition, if st reach s.length() mean we got a valid partition for given string s, then put it into ArrayList<ArrayList<String>> result;

	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 class PalindromePartitioning {
	public ArrayList<ArrayList<String>> partition(String s) {
	ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
	if (s==null||s.length()==0){
	return result;
	}
	int st=0;
	ArrayList<String> partition=new ArrayList<String>();
	buildResult(s, st, partition, result);
	return result;
	}
	private void buildResult(String s, int st, ArrayList<String> partition, ArrayList<ArrayList<String>> result){
	if (st==s.length()){
	ArrayList<String> temp=new ArrayList<String>(partition);
	result.add(temp);
	return;
	}
	for (int i=st+1; i<=s.length(); i++){
	String tempStr=s.substring(st, i);
	if (isPalindrome(tempStr)){
	partition.add(tempStr);
	buildResult(s, i, partition, result );
	partition.remove(partition.size()-1);
	}
	}
	}
	private boolean isPalindrome(String str){
	int left=0;
	int right=str.length()-1;
	while (left<right){
	if (str.charAt(left)!=str.charAt(right)){
	return false;
	}
	left++;
	right--;
	}
	return true;
	}
	}

view raw PalindromePartitioning.java hosted with ❤ by GitHub