Algorithms ladder I

24 Dec

Mission:

• lintcode 13 strStr
• lintcode 17 Subsets
• lintcode 18 SubsetsII
• lintcode 15 Permutation
• lintcode 16 Permutation II
• lintcode 594 strStr II: A lintcode-only problem, requires O(m+n) solution for substring index, see cnblog. Also see java solution Or Princeton CS Robin-Karp.

Codes:

13 strStr (easy)

Note: use two layers of iteration, complexity O(mn)

package algorithm_ladder_I;

public class StrStr {
    
    public int strStr(String source, String target) {
        // corner case;
        if (source == null || target == null) {
            return -1;
        }
        int sl = source.length();
        int tl = target.length();
        if (sl < tl) {
            return -1;
        }
        
        // two layers of iteration.
        int i, j;
        for (i = 0; i <= sl-tl; i++) {
            for (j = 0; j < tl; j++) {
                char schar = source.charAt(i + j);
                char tchar = target.charAt(j);
                if (schar != tchar) break;
                // else continue;
            }
            if (j == tl) 
                return i;
        }
        return -1;
    }
    
    public static void main(String[] args) {    
        String source = "abcdabcdefg";
        String target = "bcd";
        
        StrStr ss = new StrStr();
        System.out.println(ss.strStr(source, target)); // expected to be 1
    }
}

17 Subsets (medium)

The key of ENUMERATION is to

• Enumerate all possible values in current dimension
• then traverse to next dimension

backtracking template:

// sorting the possible values!!

int Solution[MAXDIMENSION]
       backtrack(int dimension) { // backtrack the d^th dimension. (the d^th position)
            // prune
            if (solution[] will not be an answer) return;
            
            // check if solution is one of the solution
            if (dimension == MAX_DIMENSION) {
                check and record solution[];
                return;
            }
            
            /**
             * Enumerate all possible values in current dimension
             * then traverse to next dimension
             */
            for (x = possible values of current dimension) {
                solution[dimension] = x; // solution takes x at the dimension^th position.
                backtrack(dimension+1);
            }
    }

package algorithm_ladder_I;

import java.util.ArrayList;
import java.util.List;

/**
 * lintcode 17 medium
 * use dfs:
 */
public class Subsets {
    
    public List<List<Integer>> subsets(int[] nums) {
        
            List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        
        // CORNER CASE ------------- !!!
            if (nums == null || nums.length == 0) {
                return result;
            }
        
            backtrack(nums, 0, list, result);
            return result;
    }
    
    // d for dimension/position
    private void backtrack(int[] nums, int d, List<Integer> list, List<List<Integer>> res) {
            res.add(new ArrayList<Integer>(list));
            
            for (int pos = d; pos < nums.length; pos++) { // all possible values: ranging from nums[d] to nums[nums.length-1]
                list.add(nums[pos]);
                backtrack(nums, pos+1 ,list, res);
                list.remove(list.size()-1);
            }
    }

    
    public void printList(List<Integer> list) {
            System.out.print("[");
            for (int i : list) {
                System.out.print(i + " ");
            }
            System.out.print("] \n");
    }
    
    public static void main(String[] args) {
            int[] S = new int[] {1,2,3};
            Subsets ss = new Subsets();
            List<List<Integer>> result = ss.subsets(S);
            for (List<Integer> list : result) {
                ss.printList(list);
            }
    }   
}

Subsets II

Subsets II differs from subsetsI in that

• there are duplicated elements in nums[]
• to deal with duplicated elements: for every dimension, only list the FIRST duplicated at elements.
  • e.g. [1,2_1, 2_2] for dimension = 1, visit 2_1 then ignore 2_2 (when consider dimension = 3 you can still visit 2_2);

package algorithm_ladder_I;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * with duplication
 * When enumeration for possible values, only use duplicate elements once.
 */
public class SubsetsII {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        
        // CORNER CASE ------------- !!!
            if (nums == null || nums.length == 0) {
                return result;
            }
            
            Arrays.sort(nums);
            
            backtrack(nums, 0, list, result);
            return result;
    }
    
    
    private void backtrack(int[] nums, int d, List<Integer> list, List<List<Integer>> res) {
            res.add(new ArrayList<Integer>(list));
            
            for (int i = d; i < nums.length; i++) { // enumerate all possible values at dimension d
                if (i-1 >= d) { // the previous one in nums[] may also be enumerated
                    if (nums[i] == nums[i-1]) continue; // current nums[i] will not be repeatedly enumerated.
                }
                list.add(nums[i]);
                backtrack(nums, i+1, list, res);
                list.remove(list.size()-1);
            }
    }
    
    
    public void printList(List<Integer> list) {
        System.out.print("[");
        for (int i : list) {
            System.out.print(i + " ");
        }
        System.out.print("] \n");
  }

    public static void main(String[] args) {
        int[] S = new int[] {1,2,2};
        SubsetsII ss = new SubsetsII();
        List<List<Integer>> result = ss.subsetsWithDup(S);
        for (List<Integer> list : result) {
            ss.printList(list);
        }
  } 
}

Permutation

package algorithm_ladder_I;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Permutations {
    public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        
        // CORNER CASE ------------- !!!
        if (nums == null) {
            return result;
        }
        
        Arrays.sort(nums);
        
        backtrack(nums, 0, list, result);
        return result;
    }
    
    // @Param d dimension
    private void backtrack(int[] nums, int d, List<Integer> list, List<List<Integer>> res) {
            if (list.size() == nums.length) {
                res.add(new ArrayList<Integer>(list));
                return;
            }
            
            for (int i =  0; i < nums.length; i++) {
                if (list.contains(nums[i])) continue;
                list.add(nums[i]);
                backtrack(nums, i+1, list, res);
                list.remove(list.size()-1);
            }
    }
    
    public void printList(List<Integer> list) {
        System.out.print("[");
        for (int i : list) {
            System.out.print(i + " ");
        }
        System.out.print("] \n");
    }

    public static void main(String[] args) {
        int[] S = new int[] {1,2,3};
        Permutations ss = new Permutations();
        List<List<Integer>> result = ss.permute(S);
        for (List<Integer> list : result) {
            ss.printList(list);
        }
    }
}

16 Permutation II

The key is to maintain a PossibleElement Map. e.g. for nums = [1,2,2,3]
map = {1:1, 2:2, 3:1}
In backtracking, update map when list.add(elem). i.e.

              list.add(elem); possibleElem.put(elem, possibleElem.get(elem) - 1);
               backtrack(nums, list, res);
               list.remove(list.size()-1); possibleElem.put(elem, possibleElem.get(elem) + 1);

package algorithm_ladder_I;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PermutationsII {
    
    private Map<Integer, Integer> possibleElem;
    public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        
        // CORNER CASE ------------- !!!
        if (nums == null) {
            return result;
        }
        
        Arrays.sort(nums);
        possibleElem = new HashMap<>();
        for (int i : nums) {
            possibleElem.put(i, possibleElem.getOrDefault(i, 0) + 1); 
        }
        
        backtrack(nums, list, result);
        return result;
    }
    
    // @Param d dimension
    private void backtrack(int[] nums, List<Integer> list, List<List<Integer>> res) {
            if (list.size() == nums.length) {
                res.add(new ArrayList<Integer>(list));
                return;
            }
            
            for (int elem : possibleElem.keySet()) {
                if (possibleElem.get(elem) <= 0) continue;
                list.add(elem); possibleElem.put(elem, possibleElem.get(elem) - 1);
                backtrack(nums, list, res);
                list.remove(list.size()-1); possibleElem.put(elem, possibleElem.get(elem) + 1);
            }
    }
    
    public void printList(List<Integer> list) {
        System.out.print("[");
        for (int i : list) {
            System.out.print(i + " ");
        }
        System.out.print("] \n");
    }
    
    public static void main(String[] args) {
        int[] S = new int[] {1,2,2};
        PermutationsII ss = new PermutationsII();
        List<List<Integer>> result = ss.permuteUnique(S);
        for (List<Integer> list : result) {
            ss.printList(list);
        }
    }
}

594 strStr II

Robin-Karp Algorithm -- O(m+n) complexity
Two important properties of modulation

1. (A+B) % Q = (A % Q + B % Q) % Q
2. (A * B) % Q = ((A % Q)*B) % Q
   Robin-Karp algorithm can be derived solely based on this two equations.

package algorithm_ladder_I;

/**
 * The same as LintCode 13 but requires O(m+n) Solution
 * One possible solution is Robin-Karp Algorithm
 * 1) Use HashCode use modulation: HashCode(ABCD) = (A*31^3 + B*31^2 + C*31^1 + D*31^0) % BASE (note base as Q)
 *    property of module: (A+B) % Q =  (A % Q + B % Q) % Q
 *    property of module: (A * B) % Q = ((A % Q)*B) % Q
 *      therefore,
 *      to obtain (A*31^3 + B*31^2 + C*31^1 + D*31^0) % Q  :
 *          1. cal temp = (0*31 + A) % Q 
 *          2. cal temp = (temp*31 + B) % Q
 *          3. cal temp = (temp*31 + C) % Q
 *          4. cal temp = (temp*31 + D) % Q
 * 2) If known (A*31^3 + B*31^2 + C*31^1 + D*31^0) % Q 
 *    how to obtain (B*31^3 + C*31^2 + D*31^1 + E*31^0) % Q
 *      let x = A*31^3 + B*31^2 + C*31^1 + D*31^0
 *      let x' = B*31^3 + C*31^2 + D*31^1 + E*31^0
 *      x' = x*31 + E - A*31^4
 *      x' % Q = [(x - A*31^3) * 31 + E] % Q
 *             = [x % Q + A * (Q - 31^3 % Q) + E] % Q
 *     if (31^3 % Q) = RM is calculated beforehand then
 *      x' % Q = [x % Q + A * (Q - RM) + E] % Q
 *      
 */
public class StrStrII {
    
    
    public int strStr(String haystack, String needle) {
        // corner case:
        if (haystack == null || needle == null) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }
        
        int Q = 100000;
        int M = needle.length();
        int N = haystack.length();
        
        if (M > N) {
            return -1;
        }
        
        // compute RM
        int RM = 1;
        for (int i = 1; i <= M-1; i++) {
            RM = (RM * 31) % Q;
        }
        
        int hashPattern = getHashCode(needle, Q);
        System.out.println("hashPattern: " + hashPattern);

        
        int hashCompare = getHashCode(haystack.substring(0, M), Q);
        for (int i = 0; i <= N-M; i++) {
            if (i != 0) { // update hashcode
                int originalInit = Character.getNumericValue(haystack.charAt(i-1)); 
                int newEnd = Character.getNumericValue(haystack.charAt(i+M-1));
                hashCompare = (31 * (hashCompare + originalInit * (Q - RM % Q)) + newEnd) % Q;
            }   
            System.out.println("hashCompare: " + hashCompare);
            if (hashCompare == hashPattern) {
                return i;
            } // else continue;
        }
        
        return -1;
    }
    
    private int getHashCode(String s, int Q) {
        char[] chars = s.toCharArray();
        int r = 0; 
        for (char c : chars) {
            r = (r*31 + Character.getNumericValue(c)) % Q;
        }
        return r;
    }
    
    public static void main(String[] args) {
        String haystack = "abcd";
        String needle = "bcd";
        StrStrII ss = new StrStrII();
        System.out.println(ss.strStr(haystack, needle)); // should be 1
    }   
}