This problem is from LeetCode:
http://www.programcreek.com/2013/03/leetcode-palindrome-partitioning-java/
Given a string s, partition s such that every substring of the partition is a palindrome.
we can think all possible palindromic substrings form a graph.
each palindromic substring is the node
two nodes connect each other when one's starting index is equal to
the other ending index. There are multiple roots in this graph but only one leaf.
roots are the palidrome substrings starting at index 0
leaf are the node with starting index equals to string's length
a path from root to leaf is one palindrome partition
public static void findAllPali(String s){
dfs(s, 0, new ArrayList<String>());
}
public static void dfs(String s, int start, List<String> current){
//reach leaf level, then we find the palidrome partition
if(start==s.length()){
System.out.println(current);
return;
}
for(int j=start+1;j<=s.length();j++){
//depth first search
//find one node
if(isPali(s, start, j-1)){
/*
* before we go down this branch
* we make copy of the path
* then pass it down
*/
List<String> copy = new ArrayList<String>(current);
copy.add(s.substring(start, j));
dfs(s, j, copy);
}
}
}
public static boolean isPali(String s, int i, int j){
while(i<j){
if(s.charAt(i)!=s.charAt(j))
return false;
i++;j--;
}
return true;
}
No comments:
Post a Comment