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
- (A+B) % Q = (A % Q + B % Q) % Q
- (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
}
}
