Monday, October 26, 2015

find all palidrome partitions for a string

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