lavivien
BAN USERSolution in Java, using recursion
import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
class PermIterator {
private Iterator<Set<String>> it;
int count = 0;
PermIterator (Set<Set<String>> n) {
count =n.size();
it = n.iterator();
}
public Set<String> next() {
count--;
return it.next();
}
public boolean hasNext() {
if (count > 0)
return true;
return false;
}
}
public class IteratorForPermKArrays {
public static Set<Set<String>> multiply(String[] x, String[] y, String[] z) {
List<List<String>> input = new ArrayList<>();
input.add(Arrays.asList(x));
input.add(Arrays.asList(y));
input.add(Arrays.asList(z));
Set<Set<String>> result = permK(input);
return result;
}
//Time O(nXk) = O(n^2), Space O(n^2), n is the max length of arrays, K is number of arrays
public static Set<Set<String>> permK(List<List<String>> in) {
final Set<Set<String>> out = new HashSet<Set<String>>();
permUtil(new ArrayList<List<String>>(in), new HashSet<String>(), out);
return out;
}
private static void permUtil(List<List<String>> in, Set<String> part, Set<Set<String>> out) {
if (in.isEmpty()) {
out.add(part);
return;
}
if (out.contains(part))
return;
List<List<String>> nextIn = new ArrayList<List<String>>(in);
for (String s : nextIn.remove(0)) {
Set<String> nextPart = new LinkedHashSet<String>(part);
nextPart.add(s);
permUtil(nextIn, nextPart, out);
}
}
public static void main(String[] args) {
String[] x = {"a","b","c"};
String[] y = {"p","q"};
String[] z = {"r","s"};
Set<Set<String>> result = multiply(x,y,z);
System.out.println("Permutation of arrys:");
PermIterator k = new PermIterator(result);
while(k.hasNext()){
System.out.println(k.next());
}
}
}
The dynamic solution
//Recursion + memoization(DP), Time O(n), Space O(n)
public static int wordBreakDP(Set<String> dict, String str) {
Set<String> memo = new HashSet<String>();
return wordBreakUtil(dict, str, "", memo);
}
public static int wordBreakUtil(Set<String> dict, String str, String ouput, Set<String> memo) {
int count = 0;
if (memo.contains(str))
return count + 1;
if(str.length() == 0) {
System.out.println(ouput);
return count + 1;
}
for (int i = 1; i <= str.length(); i++) {
String prefix = str.substring(0, i);
if(dict.contains(prefix)) {
memo.add(ouput + " " + prefix);
count += wordBreakUtil(dict, str.substring(i), ouput + " " + prefix, memo);
}
}
return count;
}
- lavivien April 17, 2021