Prashant Mishra

Posted on • Updated on

# All Permutations of the string

`Tc: O(2^n)`

``````import java.util.* ;
import java.io.*;
public class Solution {
public static List<String> findPermutations(String s) {
List<String> list = new ArrayList<>();
char ch[] = s.toCharArray();
int check[]  =  new int[s.length()];
getAllPermutations(ch,"",list,check);
return list;
}
public static void getAllPermutations(char[] ch, String s, List<String> list,int[] check){
if(s.length() == ch.length) {
return;
}
for(int i =0;i<ch.length;i++){
if(check[i] ==0){
check[i] = 1;
s+=ch[i];
getAllPermutations(ch,s,list,check);
s = s.substring(0,s.length()-1);
check[i] = 0;
}
}
}
}
``````

# Rat in a maze

`TC: O(4^n) as we have 4 choices at every instance, move left, right, top and bottom`

``````// m is the given matrix and n is the order of matrix
class Solution {
public static ArrayList<String> findPath(int[][] m, int n) {
ArrayList<String> list = new ArrayList<>();
getPath(0,0,m,n,"",list);

return list;
}
public static void getPath(int i, int j, int [][]m, int n, String s, ArrayList<String> list){
if(i==n-1 && j==n-1 && m[i][j]==1) {
return;
}
if(i<0 || j<0 || i>=n || j>=n || m[i][j]==0 || m[i][j] ==2) return;
m[i][j] = 2;
//left
s+="L";
getPath(i,j-1,m,n,s,list);
s = s.substring(0,s.length()-1);
//right
s+="R";
getPath(i,j+1,m,n,s,list);
s = s.substring(0,s.length()-1);
//top
s+="U";
getPath(i-1,j,m,n,s,list);
s = s.substring(0,s.length()-1);
//bottom
s+="D";
getPath(i+1,j,m,n,s,list);
s = s.substring(0,s.length()-1);
m[i][j] = 1;

}
}
``````

# Word break II similar to palindrome partitioning

Palindrome partitioning
`TC: O(2^n)`

``````import java.util.* ;
import java.io.*;
import java.util.*;

public class Solution {

public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {
ArrayList<String> list = new ArrayList<>();
HashSet<String> set  = new HashSet<>();
getWords(0,s,"",list,set);
//System.out.println(list);
return list;
}
public static void getWords(int index,String s , String temp, ArrayList<String> list,HashSet<String> set){
if(index>=s.length()){
return;
}
for(int i = index;i<s.length();i++){
if(!set.contains(s.substring(index,i+1))) continue;
int len = temp.length();
temp+=s.substring(index,i+1)+" ";
getWords(i+1,s,temp,list,set);
temp = temp.substring(0,len);
}
}
}
``````

# M-coloring

`Expected Time Complexity: O(M^N)`

``````class solve {
// Function to determine if graph can be colored with at most M colors
// such
// that no two adjacent vertices of graph are colored with same color.
public boolean graphColoring(boolean graph[][], int m, int n) {
int colorArr[] = new int[n];

return mColoringPossible(0,colorArr,n,m,graph);
}
public boolean mColoringPossible(int node, int colorArr[],int n,int m, boolean[][]graph){
if(node>=n) return true;
for(int i =1;i<=m;i++){
if(canColor(node,i,colorArr,graph)){
colorArr[node] = i;
if(mColoringPossible(node+1,colorArr,n,m,graph)) return true;
colorArr[node] =0;
}
}
return false;
}
public boolean canColor(int node, int nodeColor,int[] colorArr, boolean[][] graph){
for(int col =0;col<graph.length;col++){
if(graph[node][col]){
if(colorArr[col] ==nodeColor) return false;
}
}
return true;
}
}
``````