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;
    }

all permutations of list of characters

Given a list of unique characters, generate or print out all permutations of characters.
For example:
input: [a, b, c]
output:
[a, b, c]
[b, a, c]
[c, b, a]
[a, c, b]
[b, c, a]
[c, a, b]

One of the permutation algorithm is done by swapping,
We have a list of permutations, which initially contains the input characters only.
Then we have two loops, outer loop (i) goes through index 0 to len-2, inner loop (j) goes from index i+1 to len-1, and for each current permutation, we generate one new by swap characters at i and j.


public static void permuIteratively(char[] chars){
        assert chars!=null && chars.length>0;
       
        List<char[]> result = new ArrayList<char[]>();
        result.add(chars);
        int len = chars.length;
       
        /*
         * the algorithm is doing swapping with two loops
         * i: 0..len-2
         *   j: i+1..len-1
         *    for each string in the result list
         *     swap characters at i and j
         *     add swapping result string to the result
         *    
         * since we can't change the list which iterating through list
         * so we have to make a temp copy of the result and add swapping result
         * into temp list   
         *
         */
       
        for(int i=0; i<len-1; i++){
            //make a copy of result
            List<char[]> temp = new ArrayList<char[]>(result);
            for(int j=i+1;j<len;j++){   
                //loop through result and swap i and j
                for(char[] item : result){
                    char[] copy = Arrays.copyOf(item, item.length);
                    char tempC = copy[i];
                    copy[i] = copy[j];
                    copy[j] = tempC;
                    temp.add(copy);
                }           
            }
            result = temp;
        }
       
        for(char[] i : result){
            System.out.println(Arrays.toString(i));
        }
    }


Once we find a way do it in iteratively, it is not difficutlt to switch to recursive way .

public static void permu(char[] chars){
        List<char[]> l = new ArrayList<char[]>();
        l.add(chars);
        permuRec(chars, 0, l);
    }
    public static void permuRec(char[] chars, int index, List<char[]> current){
        /*
         * termination condition
         */
        if(index==chars.length-1){
            for(char[] i : current){
                System.out.println(Arrays.toString(i));
            }
            return;
        }
       
        //make a copy of result
        List<char[]> temp = new ArrayList<char[]>(current);
        //then we grow the result by swapping
        for(int j=index+1;j<chars.length;j++){
            for(char[] item : current){
                char[] copy = Arrays.copyOf(item, item.length);
                char tempC = copy[index];
                copy[index] = copy[j];
                copy[j] = tempC;
                temp.add(copy);
            }
        }
        //continue on next index
        permuRec(chars, index+1, temp);
    }
   

Another way to do it is to by reduction. Basically we divide and conquer,  find the permutations for substring start at i+1 first, then insert the character at i into all positions for each permutation from the subpromblem.

/**
     * we solve this by reduction, for string s,
     * first find the permutation of its substring from i+1
     * then for each permutation, insert the character at i
     * into all positions
     *
     * @param chars
     */
    public static void permutationByDP(char[] chars){
        System.out.println(permutationByReduRec(chars, 0));
    }
   
    public static List<List<Character>> permutationByReduRec(char[] chars, int index){
        /*
         * permutations are represented by list of characters
         */
        List<List<Character>> result = new ArrayList<List<Character>>();
        if(index == chars.length-1){
            /**
             * base case is the string only has one character
             */
            List<Character> list = new ArrayList<Character>();
            list.add(chars[index]);           
            result.add(list);
        }
        else{
            /*
             * we build the permutation by its substring index+1 first
             */
            List<List<Character>> list = permutationByReduRec(chars, index+1);
            char insert = chars[index];
            for(List<Character> item : list){
                /*
                 * then we insert char at index to all possible positions in the item
                 */
                for(int i=0; i<=item.size(); i++){
                    List<Character> copy = new ArrayList<Character>(item);
                    copy.add(i, insert);
                    result.add(copy);
                }

            }
        }
        return result;       
    }
   

generate super set of characters

Given a set of unique characters, generate its superset. example: a, b, c, its superset are:

[[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]]

There are two ways to solve this problem,

one is by recursion, basically we generate a set for a, then append b to each element, which itself is a set too, in the set, adding back to the set; then append c to each element in the new set and adding back to the set.
{}
{}, {a}
{b}, {a,b}, {}, {a}
{b,c{,{a,b,c},{c},{a,c},{b},{a,b},{},{a}

private static List<List<Character>> getSuperSetRec(char[] chars, int index){
        if(index == chars.length){
            List<List<Character>> list = new ArrayList<List<Character>>();
            List<Character> l = Collections.emptyList();
            list.add(l);
            return list;
        }
        else{
            List<List<Character>> list = getSuperSetRec(chars, index+1);
            List<List<Character>> res = new ArrayList<List<Character>>(list);
            for(List<Character> l : list){
                List<Character> temp = new ArrayList<Character>(l);
                temp.add(chars[index]);
                res.add(temp);
            }
            return res;
        }
    }

the second approach is very interesting. We use binary number to present each subset, 1 at any position of the binary number means the character at that position exists in the subset, e.g. 1 1 1 corresponding to {a,b,c}, 1 0 0 corresponding to {a}, so we can use 2^3 numbers to represent each subset, the problem becomes to find on every position of the binary number if it is 1 or 0.

public static void printSuperSetIteratively(char[] chars){
        int size = chars.length;
        int superSetSize = (int)Math.pow(2, size);
        List<List<Character>> list2 = new ArrayList<List<Character>>();
        for(int i=0; i<superSetSize; i++){
          
            List<Character> list = new ArrayList<Character>();
            for(int j=0; j<size; j++){
                if((i&1<<j)>0){
                    list.add(chars[j]);
                }
            }
            list2.add(list);
        }
      
        System.out.println(list2);
    }

Maximum Volume of Trapped Rain Water

I got this quiz from friend Peng Li, you can read his blog from here: http://allenlipeng47.com/PersonalPage/index/view/186/nkey.

The problem can also be found at geeksforgeeks site: http://www.geeksforgeeks.org/trapping-rain-water/

There are two approaches to solve this problem.

The first approach is to find the dividers which can trap water between them. For a bar becomes a divider, it needs to 1) no shorter than any bars on its left side up to previous divider; 2) no shorter than any bars on its right up to next divider; Essentially the dividers are local max; And the first and last bars are dividers. And if bar i is divider, then its next divider on its right meets one of the conditions
 1) taller than bar i;
 2) shorter than bar i but taller than any one else on the right.

/*
     * http://www.geeksforgeeks.org/trapping-rain-water/
     *
     * the key here is to find the dividers which can trap water between them
     * the characteristic of the dividers are they are taller than the levels between them
     *
     * and note the first and last levels are always the dividers
     */
    public static int maxTrapWater(int[] levels){
        int len = levels.length;
        /*
         * an array for each index i, it contains the index of element
         * which is larger than current levels at index i
         */
        int[] nextLarger = new int[len];
        /*
         * there is no element on the right, so set it to len
         */      
        nextLarger[len-1] = len;
        /*
         * go from right to left, for each element in the array
         * find the closest element on the right which is bigger
         * if there is none, then set its value to len
         */
        for(int i=len-2; i>=0; i--){
            int p = i+1;
            while(p<len && levels[i]>=levels[p])
                p = nextLarger[p];
            nextLarger[i] = p;
        }
      
        boolean[] isDivider = new boolean[len];
        isDivider[0] = true;
        isDivider[len-1] = true;
        int p = 0;
        while(p<len){
            int next = nextLarger[p];
            if(next == len){//levels[p] is the tallest compared to any level on the right
                isDivider[p] = true;
                p++;
            }else{
                if(isDivider[p])//levels[p] is divider, level[next] taller than that, then it is divider too
                    isDivider[next] = true;
                p = next;
            }
        }
      
        /*
         * go through dividers to calculate the water volume between them
         */
        int pre = levels[0];  
        int preIndex = 0;
        int sum = 0;
        for(int i=1; i<len; i++){
            if(isDivider[i]){
                sum += Math.min(levels[i], pre) * (i-preIndex-1);
                preIndex = i;
                pre = levels[i];
            }else
                sum -= levels[i];
        }
      
        return sum;

    }

The second approach is simpler, take any bar i, if the maximum height of bars on its right is iR and the maximum height of bars on its left is iL, then the water on top of bar i is Math.min(iR, iL) - i.

public static int maxTrapWater2(int[] levels){
        int len = levels.length;
       
        int[] leftMax = new int[len];
        leftMax[0] = levels[0];
       
        int[] rightMax = new int[len];
        rightMax[len-1] = levels[len-1];
       
        for(int i=1; i<len; i++)
            leftMax[i] = Math.max(levels[i], leftMax[i-1]);
       
        for(int i = len-2; i>=0; i--)
            rightMax[i] = Math.max(levels[i], rightMax[i+1]);
       
        int sum = 0;
        for(int i=0; i<len; i++){
            sum += Math.min(leftMax[i], rightMax[i]) - levels[i];
        }
       
        return sum;
    }


Test cases:

@Test
    public void maxTrapWater2(){
        assertEquals(2, ArrayQ.maxTrapWater2(new int[]{2,0,2}));
        assertEquals(2, ArrayQ.maxTrapWater(new int[]{2,0,2}));
       
        assertEquals(5, ArrayQ.maxTrapWater2(new int[]{2,0,1,0,3}));
        assertEquals(5, ArrayQ.maxTrapWater(new int[]{2,0,1,0,3}));
    }

Print boundary nodes of binary tree

This is from LeetCode:

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.
Variant: Print the same for a tree that is not complete.

The key to solve this problem is to understand recursion and how we use it. Recursion can be done by bottom-up or top-down fashion. Bottom-up approach is to build up the stack until hitting the bottom then start to present the result, top-down approach is to present the result along the way to bottom and terminate at the bottom.

Here is the code. The comments explain what each method tries to accomplish.

    public static class Tree {
        int v;
        Tree left;
        Tree right;
        public Tree(int v){
            this.v = v;
        }
        public Tree(int v, Tree left, Tree right){
            this.v = v;
            this.left = left;
            this.right = right;
        }
    }
  
    public static void printBoundary(Tree root){
        //print left-most from top to bottom
        Tree curr = root;
        printLeftMost(curr);
        //print leaves from left to right
        printLeavesLeftRight(root);
        //print right-most from bottom to top
        printRightMost(root, root);
    }
  
    /**
     * print the right most nodes bottom up
     * and skip the first and last
     * @param root
     * @param first
     */
    public static void printRightMost(Tree root, Tree top){
        if(root.right!=null)
            printRightMost(root.right, top);
        else if(root.left!=null)
            printRightMost(root.left, top);
        if(root!=top && root.left!=null && root.right!=null)
            System.out.println(root.v);
    }
    /**
     * print leaves from left to right
     * and skip the left most leaf
     * and return the last one
     * @param root
     * @param start
     * @return
     */
    public static void printLeavesLeftRight(Tree root){
        if(root==null)
            return;
        printLeavesLeftRight(root.left);
        if(root.left==null && root.right==null){
            System.out.println(root.v);
        }
        printLeavesLeftRight(root.right);
    }
    /**
     * print left most nodes from top to bottom
     * and skip/return the last one
     * @param root
     * @return
     */
    public static void printLeftMost(Tree root){
        if(root.left==null && root.right==null)  
            return;
        System.out.println(root.v);
        if(root.left!=null)
            printLeftMost(root.left);
        else
            printLeftMost(root.right);
    }

Break compound word into multiple words

A compound word is a word which can be broken into multiple words. For example: appletree can be broken to apple and tree. Note a single word is not compound word, and a compound word may be broken into words in different ways, for example, autopay can be broken into au, to, pay, Or auto, pay.

Here we use woomom as example, and assume we have a helper function isWord(String w) which can tell us if any string is word or not.

    /*
     * woomom = woo + mom Or woom + om
     */
    static boolean isWord(String w){
        return w.equals("woom") || w.equals("woo") || w.equals("om") || w.equals("mom");
    }
   
    public static String printCompoundWord(String w){
        return printCompoundWordRec(w, 0, 0);
    }
   
    public static String printCompoundWordRec(String w, int start, int found){
        if(start == w.length()){
            return found>1?"":null;
        }
       
        for(int i=start+1; i<=w.length(); i++){
            if(isWord(w.substring(start, i))){
                String s  = printCompoundWordRec(w, i, found+1);
                if(s!=null){
                    String re = w.substring(start, i) + "-" + s;
                    if(found==0){
                        System.out.println(re);
                    }else
                        return re;
                   
                }
            }
        }
       
        return null;
    }

Here is iterative approach to check if word is compound word.