chris
BAN USERBelow is the code using Iterative approach.
1. Find all combinations sum to string length using 1's & 2's
2. Find possible words for each combination
import java.util.ArrayList;
public class StringAlgorithms {
public static ArrayList<String> getPossibleWords(String str) {
ArrayList<ArrayList<Integer>> combinations = getLengthCombinations(str.length());
ArrayList<String> result = new ArrayList<String>();
String letters = " abcdefghijklmnopqrstuvwxyz";
for (ArrayList<Integer> list : combinations) {
int lastPos = 0;
String currentWord = "";
boolean found = true;
for (Integer count : list) {
String s = str.substring(lastPos, lastPos + count);
int letterPosition = Integer.parseInt(s);
if (letterPosition >= letters.length()) {
found = false;
break;
}
currentWord += letters.charAt(letterPosition);
lastPos += count;
}
if (found) result.add(currentWord);
}
return result;
}
private static ArrayList<ArrayList<Integer>> getLengthCombinations(int n) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i <= n / 2; i++) {
ArrayList<Integer> value = new ArrayList<Integer>();
for (int j = 0; j < n - 2 * i; j++) value.add(1);
for (int j = 0; j < i; j++) value.add(2);
while (value != null) {
result.add(value);
value = getNextCombination(value);
}
}
return result;
}
private static ArrayList<Integer> getNextCombination(ArrayList<Integer> values) {
int i;
ArrayList<Integer> result = new ArrayList<Integer>();
result.addAll(values);
for (i = values.size() - 2; i >= 0; i--) {
if (values.get(i) == 1 && values.get(i + 1) == 2) break;
}
if (i == -1) return null;
swap(result, i, i + 1);
sortElements(result, i + 1, result.size() - 1);
return result;
}
private static void sortElements(ArrayList<Integer> values, int start, int end) {
for (int i = start; i < end; i++) {
for (int j = i + 1; j <= end; j++) {
if (values.get(i) > values.get(j)) {
swap(values, i, j);
}
}
}
}
private static void swap(ArrayList<Integer> array, int i, int j) {
int temp = array.get(i);
array.set(i, array.get(j));
array.set(j, temp);
}
}
I'm not sure whether this makes much sense but I have a doubt.
Can the max sequence branch out? In other words, do we need to find the longest sequence or maximum block? Refer to the below example.
Given Matrix
2, 3, 4, 5
6, 4, 8, 9
9, 5, 10, 11
7, 6, 5, 6
In the below, which is the correct one?
2, 3, 4, 5
-, 4, -, -
-, 5, -, -
7, 6, 5, 6
(or)
-, 3, 4, 5
-, 4, -, -
-, 5, -, -
-, 6, 5, 6
Here is solution in java. Just find the minimum number of boards required first and check for all the combinations. In this case, we check for many combinations (sub problems) again and again. If there is a way to store this result in some DS, we can improve the performance through dynamic programming.
public static int possibleWays(int n, int m, int k) {
/* c -> minimum board required */
int c = n / m * k;
int total = 0;
if (n % m > m - k) c += n % m - (m - k);
int array[] = new int[n];
for (int i = 0; i < n; i++) {
if (i >= n - c) array[i] = 1;
else array[i] = 0;
}
do {
if (validateCombination(array, m, k)) total++;
} while(nextCombination(array));
return total;
}
private static boolean nextCombination(int[] array) {
boolean swapFound = false;
int i, j;
int n = array.length;
for (i = n - 1; i > 0; i--)
if (array[i] == 1 && array[i - 1] == 0) break;
if (i == 0) return false;
for (j = i - 1; j >= 0; j--)
if (array[j] == 0) {
swapFound = true;
break;
}
if (swapFound) {
swap(array, i, j);
/* Sort bit array after swapping */
int k = i;
for (int i1 = i; i1 < n; i1++) {
if (array[i1] < array[k]) {
swap(array, i1, k);
k++;
}
else if (array[i1] > array[k]) {
k++;
}
}
}
return swapFound;
}
private static boolean validateCombination(int[] array, int m, int k) {
int n = array.length;
for (int i = 0; i <= n - m; i++) {
int tempK = k;
for (int j = i; j < i + m; j++)
if (array[j] == 1) tempK--;
if (tempK > 0) return false;
}
return true;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static char[] replace_b_ac(char[] array) {
int j = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] != 'b') {
if (array[i] == 'c' && j > 0 && array[j - 1] == 'a') {
j--;
} else {
array[j] = array[i];
j++;
}
}
}
for (int k = j; k < array.length; k++) array[k] = '\0';
return array;
}
Here is recursive solution in java.
private static int listSize(ListNode node) {
if (node == null) return 0;
return listSize(node.next) + 1;
}
public static int sumLinkedLists (ListNode list1, ListNode list2) {
return sumLinkedLists(list1, list2, listSize(list1) - 1);
}
private static int sumLinkedLists (ListNode list1, ListNode list2, int digitPos) {
if (list1 == null || list2 == null) return 0;
int recursiveSum = sumLinkedLists(list1.next, list2.next, digitPos - 1);
int sum = list1.data + list2.data;
recursiveSum = recursiveSum + sum * (int) Math.pow(10, digitPos);
return recursiveSum;
}
It looks like it follows a pattern.
1. Find N, the nearest power of 2 and check for numbers
N + {(2^0), (2^1), (2^2, 2^2 + 1), (2^3, 2^3 + 1, 2^3 + 2), (2^4, 2^4 + 1, 2^4 + 2, 2^4 + 3) and so on}
2. Exclude N + N/2
3. Stop the loop once calculated value is greater than given number.
For Example, If Given number is 10
- chris March 31, 2015Find N = 2 ^ 3 = 8
Now try
8 + 2^0 = 9 < Given Number so continue
8 + 2^1 = 10 = Given Number so continue
Ignore 2^2 as It is equal to N/2.
8 + 2^3 = 16 > Given Number so Return 16