-
Notifications
You must be signed in to change notification settings - Fork 2
Recursion Problems and Patterns
Mani Bhushan edited this page Aug 28, 2016
·
52 revisions
The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.
The algorithm is a simple recursive algorithm, from each cell first print all paths by
going down and then print all paths by going right. Do this recursively for each cell encountered.
Input:
int[][] M = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
Output:
[1, 4, 7, 8, 9]
[1, 4, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 2, 5, 6, 9]
[1, 2, 3, 6, 9]
public void printPaths(int [][] M) {
int i=0, j=0;
int len = M.length + M[0].length-1;
List<Integer> path = new ArrayList<Integer>();
for (int x=0; x<len; x++) {
path.add(0);
}
printPaths(M, i, j, path);
}
private void printPaths(int [][] M, int i, int j, List<Integer> path) {
if (i == M.length-1 && j == M[0].length-1) {
path.set(i+j, M[i][j]);
System.out.println(path.toString());
}
if (i >= M.length || j >= M[0].length) {
return;
}
path.set(i+j, M[i][j]);
printPaths(M, i+1, j, path);
printPaths(M, i, j+1, path);
}
An edit between two strings is one of the following changes.
Add a character
Delete a character
Change a character
Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit.
Expected time complexity is O(m+n) where m and n are lengths of two strings.
Examples:
Input: s1 = "geeks", s2 = "geek"
Output: yes
Number of edits is 1
Input: s1 = "geeks", s2 = "geeks"
Output: no
Number of edits is 0
Input: s1 = "geaks", s2 = "geeks"
Output: yes
Number of edits is 1
Input: s1 = "peaks", s2 = "geeks"
Output: no
Number of edits is 2
public boolean isOneEdit(String A, String B) {
if (A == null || B == null) {
return false;
}
int alen = A.length();
int blen = B.length();
if (Math.abs(alen - blen) > 1) {
return false;
}
int i = 0;
int j = 0;
int dist = isOneEdit(A.toCharArray(), i, B.toCharArray(), j);
return dist == 1;
}
private int isOneEdit(char[] A, int i, char[] B, int j) {
if (i == A.length) {
return B.length - j;
} else if (j == B.length) {
return A.length - i;
}
if (A[i] == B[j]) {
return isOneEdit(A, i + 1, B, j + 1);
} else {
return 1 + Math.min(
isOneEdit(A, i + 1, B, j + 1),
Math.min(isOneEdit(A, i + 1, B, j),
isOneEdit(A, i, B, j + 1)));
}
}
(9). Given nxn board place n queen on this board so that they dont attack each other. One solution is to find any placement of queens which do not attack each other. Other solution is to find all placements of queen on the board.
queen = 4;
queen placements:
[0, 1]
[1, 3]
[2, 0]
[3, 2]
public void placeQueens(int numQueen) {
Cell [] cells = new Cell[numQueen];
int row = 0;
placeQueens(numQueen, row, cells);
System.out.println("queen placements: ");
for (Cell cell: cells) {
System.out.println(cell.toString());
}
}
private boolean placeQueens(int numQueen, int row, Cell [] cells) {
if (row == numQueen) {
return true;
}
for (int col=0; col < numQueen; col++) {
boolean found = true;
for (int queen=0; queen<row; queen++) {
if (cells[queen].row == row || cells[queen].col == col || cells[queen].row - cells[queen].col == row-col ||
cells[queen].row + cells[queen].col == row+col) {
found = false;
break;
}
}
if (found) {
cells[row] = new Cell(row, col);
if (placeQueens(numQueen, row+1, cells)) {
return true;
}
}
}
return false;
}
class Cell {
int row;
int col;
Cell(int x, int y) {
this.row = x;
this.col = y;
}
public String toString() {
return "[" + this.row + ", " + this.col + "]";
}
}
Imagine x is an operand and * is a binary operator. We say a string
of x and * follows Reverse Polish notation if it is a postfix notation.
For example strings xx*, x, and xx*xx** follow Reverse Polish notation.
Given a string of x and *, how many insert, delete, and replace operations
are needed to make the string follow the RPN.
For example, xx* need 0 operation to follow RPN since it already follows RPN.
x*x needs two operations to become xx* which follows RPN.
*xx* needs one operation to become xx* which follows RPN.
public int minEdits(String input) {
if (input == null || input.length() < 1) {
return 0;
}
char [] A = input.toCharArray();
int index = 0;
int xCount = 0;
return minEdits(A, index, xCount);
}
private int minEdits(char [] A, int index, int xCount) {
if (index == A.length) {
return (xCount == 1) ? 0: Integer.MAX_VALUE;
}
if (A[index] == 'x') {
//we can use the x as it is, delete it or replace it with *
//a. using as it is
int v1 = minEdits(A, index+1, xCount+1);
//b. deleting it
int v2 = Integer.MAX_VALUE;
if (xCount > 1) {
v2 = minEdits(A, index+1, xCount-1);
v2 = (v2 != Integer.MAX_VALUE) ? v2+1: Integer.MAX_VALUE;
}
//c. replace it with *
int v3 = minEdits(A, index+1, xCount);
v3 = (v3 != Integer.MAX_VALUE) ? v3+1: Integer.MAX_VALUE;
return Math.min(v1, Math.min(v2, v3));
} else {
//if its * then we can reduce 2 x to 1 x, delete it or replace with x
int v0 = Integer.MAX_VALUE;
if (xCount >= 2) {
v0 = minEdits(A, index+1, xCount-1);
//v0 = (v0 != Integer.MAX_VALUE) ? v0 +1: Integer.MAX_VALUE;
}
int v1 = minEdits(A, index+1, xCount);
v1 = (v1 != Integer.MAX_VALUE) ? v1 +1: Integer.MAX_VALUE;
int v2 = minEdits(A, index+1, xCount+1);
v2 = (v2 != Integer.MAX_VALUE) ? v2+1: Integer.MAX_VALUE;
return Math.min(v0, Math.min(v1, v2));
}
}
(7). Letter Combinations of a Phone Number. Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given.
map.put(2, "abc");
map.put(3, "def");
map.put(4, "ghi");
map.put(5, "jkl");
map.put(6, "mno");
map.put(7, "pqrs");
map.put(8, "tuv");
map.put(9, "wxyz");
map.put(0, "");
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
public void letterCombinations(int [] A) {
int index = 0;
StringBuffer sb = new StringBuffer();
letterCombination(A, index, sb);
}
private void letterCombination(int [] A, int index, StringBuffer sb) {
if (index == A.length) {
if (sb.length() == A.length) {
System.out.print(sb.toString() + " ");
}
}
for (int i=index; i<A.length; i++) {
String str = map.get(A[i]);
char [] chArr = str.toCharArray();
for (int j=0; j<chArr.length; j++) {
sb.append(chArr[j]);
letterCombination(A, i+1, sb);
sb.deleteCharAt(sb.length()-1);
}
}
}
(6). Consider a coding system for alphabets to integers where ‘a’ is represented as 1, ‘b’ as 2, .. ‘z’ as 26. Given an array of digits (1 to 9) as input, write a function that prints all valid interpretations of input array.
Examples:
Input: {1, 1}
Output: ("aa", 'k")
[2 interpretations: aa(1, 1), k(11)]
Input: {1, 2, 1}
Output: ("aba", "au", "la")
[3 interpretations: aba(1,2,1), au(1,21), la(12,1)]
Input: {9, 1, 8}
Output: {"iah", "ir"}
[2 interpretations: iah(9,1,8), ir(9,18)]
public int countInterpretations(int []A) {
int index = 0;
StringBuffer sb = new StringBuffer();
return countInterpretations(A, index, sb);
}
private int countInterpretations(int [] A, int index, StringBuffer sb) {
if (index >= A.length) {
System.out.print(sb.toString() + " ");
return 1;
}
int count = 0;
sb.append(hmap.get(A[index]));
count += countInterpretations(A, index+1, sb);
sb.deleteCharAt(sb.length()-1);
if (index+1 < A.length) {
int num = A[index]*10 + A[index+1];
if (num > 9 && num < 27) {
sb.append(hmap.get(num));
count += countInterpretations(A, index+2, sb);
sb.deleteCharAt(sb.length()-1);
}
}
return count;
}
Input: {a,b,c};
Output:
* * *
a * *
a b *
a b c
a * c
* b *
* b c
* * c
public void printCombination(char[] A) {
int index = 0;
boolean[] result = new boolean[A.length];
printCombinationUtil(A, index, result);
}
private void printCombinationUtil(char[] A, int index, boolean[] result) {
for (int i = 0; i < result.length; i++) {
if (result[i]) {
System.out.print(A[i] + " ");
} else {
System.out.print("* ");
}
}
System.out.println();
for (int i = index; i < A.length; i++) {
result[i] = true;
printCombinationUtil(A, i + 1, result);
result[i] = false;
}
}
Input: {1, 2, 1, 3};
Output:
[1, 1]
[1, 2]
[1, 3]
[2, 3]
public void printCombination(int [] A, int k) {
int index = 0;
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(A);
printCombinationUtil(A, k, index, list);
}
private void printCombinationUtil(int [] A, int k, int index, List<Integer> list) {
if (list.size() == k) {
System.out.println(list.toString());
}
if (index >= A.length) {
return;
}
for (int i=index; i<A.length; i++) {
if (i != index && A[i] == A[i-1]) continue;
list.add(A[i]);
printCombinationUtil(A, k, i+1, list);
list.remove(list.size()-1);
}
}
Input: {1,2,3,4}
Output:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
public void printCombination(int [] A, int k) {
int index = 0;
List<Integer> list = new ArrayList<Integer>();
printCombinationUtil(A, k, index, list);
}
private void printCombinationUtil(int [] A, int k, int index, List<Integer> list) {
if (list.size() == k) {
System.out.println(list.toString());
}
if (index >= A.length) {
return;
}
for (int i=index; i<A.length; i++) {
//if (i != index && A[i] == A[i-1]) continue;
list.add(A[i]);
printCombinationUtil(A, k, i+1, list);
list.remove(list.size()-1);
}
}
Input: [a, b, c]
Output:
[a]
[a, b]
[a, b, c]
[a, c]
[b]
[b, c]
[c]
public void printCombinations(char [] input) {
int index = 0;
List<Character> list = new ArrayList<Character>();
printCombinationUtil(input, index, list);
}
private void printCombinationUtil(char [] input, int index, List<Character> list) {
if (list.size() > 0) {
System.out.println(list.toString());
}
for (int i=index; i<input.length; i++) {
if (i != index && input[i] == input[i-1]) {
continue;
}
list.add(input[i]);
printCombinationUtil(input, i+1, list);
list.remove(list.size()-1);
}
}
A string X can be put before another string Y in circle if the last character of X is same as first character of Y
Input: {"for", "geek", "rig", "kaf"}
Output: Yes
public boolean wordCircle(String [] words) {
int index = 1;
char prev = words[0].charAt(words[0].length()-1);
return wordCircle(words, index, prev);
}
private boolean wordCircle(String [] words, int index, char prev) {
if (index == words.length) {
System.out.println(Arrays.toString(words));
return prev == words[0].charAt(0);
}
for (int i=index; i<words.length; i++) {
if(words[i].charAt(0) == prev) {
String tmp = words[index];
words[index] = words[i];
words[i] = tmp;
boolean result = wordCircle(words, index+1, words[index].charAt(words[index].length()-1));
if (result) {
return true;
}
}
}
return false;
}