https://leetcode.com/problems/palindrome-partitioning/
Solution Reference:
http://www.programcreek.com/2013/03/leetcode-palindrome-partitioning-java/
package palindrome_partioning;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
public class Solution {
public static void main (String args[])
{
Solution s1 = new Solution();
String input = "aab";
System.out.println(s1.partition(input));
}
public static ArrayList<ArrayList<String>> partition(String a)
{
ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
if(a==null||a.length()==0)
{
return res;
}
ArrayList<String> temp = new ArrayList<String>();
partition(a,temp,res,0);
return res;
}
public static void partition(String a,ArrayList<String> temp,ArrayList<ArrayList<String>> res,int start)
{
if(start==a.length())
{
res.add(new ArrayList(temp));
return;
}
for(int i = start+1;i<=a.length();i++)
{
if(isPalindrome(a.substring(start, i)))
{
temp.add(a.substring(start,i));
partition(a,temp,res,i);
temp.remove(temp.size()-1);
}
}
}
public static boolean isPalindrome(String input)
{
int start = 0,end=input.length()-1;
while(start<=end)
{
if(input.charAt(start)!=input.charAt(end))
{
return false;
}
start++;
end--;
}
return true;
}
}
Tracing the above program for input string "aab"
start = 0i= 1
subString isa
start = 1i= 2
subString isa
start = 2i= 3
subString isb
start equals to length of the string hence:
result arraylist at the end of this start=3is[[a, a, b]]
start = 1i= 3
No substring in this iteration since ab is not a palindrome
start = 0i= 2
subString isaa
start = 2i= 3
subString isb
start equals to length of the string hence:
result arraylist at the end of this start=3is[[a, a, b], [aa, b]]
start = 0i= 3
No substring in this iteration since aab is not a palindrome
final output list is[[a, a, b], [aa, b]]
Tracing the above program for input string "helloworld"
start = 0i= 1
subString ish
start = 1i= 2
subString ise
start = 2i= 3
subString isl
start = 3i= 4
subString isl
start = 4i= 5
subString iso
start = 5i= 6
subString isw
start = 6i= 7
subString iso
start = 7i= 8
subString isr
start = 8i= 9
subString isl
start = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d]]
start = 8i= 10
No substring in this iteration since ld is not a palindrome
start = 7i= 9
No substring in this iteration since rl is not a palindrome
start = 7i= 10
No substring in this iteration since rld is not a palindrome
start = 6i= 8
No substring in this iteration since or is not a palindrome
start = 6i= 9
No substring in this iteration since orl is not a palindrome
start = 6i= 10
No substring in this iteration since orld is not a palindrome
start = 5i= 7
No substring in this iteration since wo is not a palindrome
start = 5i= 8
No substring in this iteration since wor is not a palindrome
start = 5i= 9
No substring in this iteration since worl is not a palindrome
start = 5i= 10
No substring in this iteration since world is not a palindrome
start = 4i= 6
No substring in this iteration since ow is not a palindrome
start = 4i= 7
subString isowo
start = 7i= 8
subString isr
start = 8i= 9
subString isl
start = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d]]
start = 8i= 10
No substring in this iteration since ld is not a palindrome
start = 7i= 9
No substring in this iteration since rl is not a palindrome
start = 7i= 10
No substring in this iteration since rld is not a palindrome
start = 4i= 8
No substring in this iteration since owor is not a palindrome
start = 4i= 9
No substring in this iteration since oworl is not a palindrome
start = 4i= 10
No substring in this iteration since oworld is not a palindrome
start = 3i= 5
No substring in this iteration since lo is not a palindrome
start = 3i= 6
No substring in this iteration since low is not a palindrome
start = 3i= 7
No substring in this iteration since lowo is not a palindrome
start = 3i= 8
No substring in this iteration since lowor is not a palindrome
start = 3i= 9
No substring in this iteration since loworl is not a palindrome
start = 3i= 10
No substring in this iteration since loworld is not a palindrome
start = 2i= 4
subString isll
start = 4i= 5
subString iso
start = 5i= 6
subString isw
start = 6i= 7
subString iso
start = 7i= 8
subString isr
start = 8i= 9
subString isl
start = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d], [h, e, ll, o, w, o, r, l, d]]
start = 8i= 10
No substring in this iteration since ld is not a palindrome
start = 7i= 9
No substring in this iteration since rl is not a palindrome
start = 7i= 10
No substring in this iteration since rld is not a palindrome
start = 6i= 8
No substring in this iteration since or is not a palindrome
start = 6i= 9
No substring in this iteration since orl is not a palindrome
start = 6i= 10
No substring in this iteration since orld is not a palindrome
start = 5i= 7
No substring in this iteration since wo is not a palindrome
start = 5i= 8
No substring in this iteration since wor is not a palindrome
start = 5i= 9
No substring in this iteration since worl is not a palindrome
start = 5i= 10
No substring in this iteration since world is not a palindrome
start = 4i= 6
No substring in this iteration since ow is not a palindrome
start = 4i= 7
subString isowo
start = 7i= 8
subString isr
start = 8i= 9
subString isl
start = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d], [h, e, ll, o, w, o, r, l, d], [h, e, ll, owo, r, l, d]]
start = 8i= 10
No substring in this iteration since ld is not a palindrome
start = 7i= 9
No substring in this iteration since rl is not a palindrome
start = 7i= 10
No substring in this iteration since rld is not a palindrome
start = 4i= 8
No substring in this iteration since owor is not a palindrome
start = 4i= 9
No substring in this iteration since oworl is not a palindrome
start = 4i= 10
No substring in this iteration since oworld is not a palindrome
start = 2i= 5
No substring in this iteration since llo is not a palindrome
start = 2i= 6
No substring in this iteration since llow is not a palindrome
start = 2i= 7
No substring in this iteration since llowo is not a palindrome
start = 2i= 8
No substring in this iteration since llowor is not a palindrome
start = 2i= 9
No substring in this iteration since lloworl is not a palindrome
start = 2i= 10
No substring in this iteration since lloworld is not a palindrome
start = 1i= 3
No substring in this iteration since el is not a palindrome
start = 1i= 4
No substring in this iteration since ell is not a palindrome
start = 1i= 5
No substring in this iteration since ello is not a palindrome
start = 1i= 6
No substring in this iteration since ellow is not a palindrome
start = 1i= 7
No substring in this iteration since ellowo is not a palindrome
start = 1i= 8
No substring in this iteration since ellowor is not a palindrome
start = 1i= 9
No substring in this iteration since elloworl is not a palindrome
start = 1i= 10
No substring in this iteration since elloworld is not a palindrome
start = 0i= 2
No substring in this iteration since he is not a palindrome
start = 0i= 3
No substring in this iteration since hel is not a palindrome
start = 0i= 4
No substring in this iteration since hell is not a palindrome
start = 0i= 5
No substring in this iteration since hello is not a palindrome
start = 0i= 6
No substring in this iteration since hellow is not a palindrome
start = 0i= 7
No substring in this iteration since hellowo is not a palindrome
start = 0i= 8
No substring in this iteration since hellowor is not a palindrome
start = 0i= 9
No substring in this iteration since helloworl is not a palindrome
start = 0i= 10
No substring in this iteration since helloworld is not a palindrome
final output list is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d], [h, e, ll, o, w, o, r, l, d], [h, e, ll, owo, r, l, d]]
No comments:
Post a Comment