jcgarciarojas
BAN USERpublic String swap(Pair index, String str) {
char [] charArray = str.toCharArray();
char temp = charArray[index.y];
charArray[index.y] = charArray[index.x];
charArray[index.x] = temp;
return String.valueOf(charArray);
}
public String permutations(List<Pair> indexes, String initialStr) {
System.out.println("initialStr "+initialStr);
int numberPermuations = indexes.size();
String resultStr = initialStr;
HashSet<String> permutations = new HashSet<String>();
String tempStr = initialStr;
while (true) {
List<String> tmpPermutations = new ArrayList<String>();
for (Pair p: indexes) {
tempStr = swap(p, tempStr);
if (initialStr.equals(tempStr) || permutations.contains(tempStr))
break;
tmpPermutations.add(tempStr);
//get greater lexicographic element
if (tempStr.compareTo(resultStr) > 0)
resultStr = tempStr;
}
//if expected number of permutations not perform then exit;
if (tmpPermutations.size() < numberPermuations)
break;
permutations.addAll(tmpPermutations);
}
System.out.println(permutations);
System.out.println("resultStr "+resultStr);
return resultStr;
}
output
=====
initialStr abdc
[cbda, dbca, cbad, dbac] ==> this doesn't come in order of addition due to it is a HashSet. But HashSet is based on HashMap so it is better to use it than a list.
resultStr dbca
This is with a single while but it is too complicated because I need one pointer to the head and one to the current element. I prefer mergeTwoSortedLinkList with recursion. It is more elegant.
public LinkedList merger(LinkedList l1, LinkedList l2){
LinkedList tmp = null;
LinkedList result = null;
while(true) {
if (l1 == null && l2 == null) break;
if (l2 == null || (l1 != null && l1.value <= l2.value)) {
if (tmp == null) {
tmp = l1;
result = tmp;
}
else {
tmp.setNext(l1);
tmp = tmp.next();
}
l1 = l1.next();
}
else if (l1 == null || (l2 != null && l1.value > l2.value)) {
if (tmp == null) {
tmp = l2;
result = tmp;
}
else {
tmp.setNext(l2);
tmp = tmp.next();
}
l2 = l2.next();
}
}
return result;
}
My Solution uses branch and bound (B&B) with dynamic programming using distance travelled to estimate the closest guard. drawback is sorting
time complexity and size is 0(n^2).
- jcgarciarojas May 27, 2016