Daily Archives: October 23, 2015

Today, I found a great coding style for series problem, like permutation, subset and group of palindrome:

public static void getPermutationUtil(String str, int start, List<List<String>> result, List<String> currResult) {
    if(start==str.length()) {
        ArrayList<String> curr = new ArrayList<String>(currResult);
        result.add(curr);
    }
    else {
        for(int i=start; i<str.length(); i++) {
            String currStr = str.substring(start, i+1);
            currResult.add(currStr);
            getPermutationUtil(str, i + 1, result, currResult);
            currResult.remove(currResult.size()-1);
        }
    }
}

When we construct a subset of an array, we try to build it on arr[start,…,length-1]. The arr[0,…,i-1] is already done and saved in currResult. When start equals length, it means it ends and we save this currResult in result. Below are the 3 types of application of this coding style:
Permutation

public static List<List<String>> getPermutation(String str) {
    List<List<String>> result = new ArrayList<List<String>>();
    getPermutationUtil(str, 0, result, new ArrayList<String>());
    return result;
}

public static void getPermutationUtil(String str, int start, List<List<String>> result, List<String> currResult) {
    if(start==str.length()) {
        ArrayList<String> curr = new ArrayList<String>(currResult);
        result.add(curr);
    }
    else {
        for(int i=start; i<str.length(); i++) {
            String currStr = str.substring(start, i+1);
            currResult.add(currStr);
            getPermutationUtil(str, i + 1, result, currResult);
            currResult.remove(currResult.size()-1);
        }
    }
}

SuperSet, This is the same problem from here, which is a another solution.

public static List<List<Character>> getSuperSet(char[] chs) {
    List<List<Character>> result = new ArrayList<List<Character>>();
    getSuperSetUtil(chs, 0, result, new ArrayList<Character>());
    return result;
}

public static void getSuperSetUtil(char[] chs, int start, List<List<Character>> result, List<Character> currResult) {
    if(start==chs.length) {
        ArrayList<Character> curr = new ArrayList<Character>(currResult);
        result.add(curr);
    }
    else {
        //count current char
        currResult.add(chs[start]);
        getSuperSetUtil(chs, start + 1, result, currResult);
        currResult.remove(currResult.size()-1);
        //doesn't count current char
        getSuperSetUtil(chs, start+1, result, currResult);
    }
}

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

All Palindrome Partition

public static List<List<String>> getAllPalindromePartition(String str) {
    List<List<String>> result = new ArrayList<List<String>>();
    getAllPalindromePartitionUtil(str, 0, result, new ArrayList<String>());
    return result;
}

public static void getAllPalindromePartitionUtil(String str, int start, List<List<String>> result, List<String> currResult) {
    if(start==str.length()) {
        ArrayList<String> curr = new ArrayList<String>(currResult);
        result.add(curr);
    }
    else {
        for(int i=start; i<str.length(); i++) {
            String currStr = str.substring(start, i+1);
            if(isPalindrome(currStr)) {
                currResult.add(currStr);
                getAllPalindromePartitionUtil(str, i + 1, result, currResult);
                currResult.remove(currResult.size()-1);
            }
        }
    }
}

public static boolean isPalindrome(String str) {
    int left=0, right=str.length()-1;
    while(left<right) {
        if(str.charAt(left)==str.charAt(right)) {
            left++;
            right--;
        }
        else {
            return false;
        }
    }
    return true;
}

Check my code on github:Permutation, Subset, All palindrome sets