InterviewBit Backtracking Combinations

Question Reference:

http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

Print all possible combinations of r elements in a given array of size n

Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is {1, 2, 3, 4} and r is 2, then output should be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}.

Solution in java
main view point is we can take the element at index i as part of out subset in this instance or we can ignore this index and go to next index.
i.e.,
when n = 4 we have elements from 1,2,3,4
and k = 2i.e., we can take 2 elements
Now we can take 1,2 or leave 2 and go for 3 i.e., 1,3 or leave 3 go for 4 i.e., 1,4
so 1,2 1,3 1,4

when we have 2 as starting element we can have 2,3 or 2,4
and for 3 we have 3,4
Solution in Java(After practicing couple of similar problems i was able to implement it on my own based on above hint finally feeling happy for this :))

package Combinations;

import java.util.*;

public class Solution {

public ArrayList<ArrayList<Integer>> combine(int n, int k) 

{

   

  ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

  ArrayList<Integer> temp = new ArrayList<Integer>();

  combinations(res,temp,n,k,0,1);

  return res;

   

   

}

public static void combinations(ArrayList<ArrayList<Integer>> res,ArrayList<Integer> temp,int n,int k,int count,int index)

{

        if(count>=k)

        {

            res.add(new ArrayList(temp));

            

            return;

        }

        if(index>n)

{

return;

}

        else

        {

            //for(int i =index;i<=n;i++)

            //{

                temp.add(index);

                combinations(res,temp,n,k,count+1,index+1);

                temp.remove(temp.size()-1);

                combinations(res,temp,n,k,count,index+1);

            //}

        }

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Solution s1 = new Solution();

System.out.println(s1.combine(5, 4));

}

}

GeeksForGeeks Print all combinations of balanced parentheses

Question reference

http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/

Write a function to generate all possible n pairs of balanced parentheses. 

For example, if n=1
{}
for n=2
{}{}
{{}}

I understood implementation from below  references

http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/

https://discuss.leetcode.com/topic/8724/easy-to-understand-java-backtracking-solution/2

Solution in Java

View point is that the no of "(" is equal to ")"

package generate_all_paranthesis;

import java.util.*;

public class Solution1 {

public ArrayList<String> generateParenthesis(int a) 

{

    ArrayList<String> res = new ArrayList<String>();

    if(a==0)

    {

    return res;

    }    

    backtracking(0,0,a,new StringBuilder(),res);

    return res;

}

public static void backtracking(int open,int close,int a,StringBuilder temp,ArrayList<String> res)

{

if(close==a)

{

res.add(temp.toString());

return;

}

else

{

           //go on adding ")" if open > close

if(open>close)

{

                                //appending ")"
                temp.append(")");

backtracking(open, close+1, a, temp, res);

temp.setLength(temp.length()-1);

                                //removing ")"

}

           //go on adding "(" if open <n

if(open<a)

{

                                //appending "("

                                temp.append("(");

backtracking(open+1, close, a, temp, res);

temp.setLength(temp.length()-1);

                                //removing "("

}

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

      Solution1 s1 = new Solution1();

      System.out.println(s1.generateParenthesis(3));

}

}

GeeksForGeeks Boggle Solver : Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Reference :http://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
       boggle[][]   = {{'G','I','Z'},
                       {'U','E','K'},
                       {'Q','S','E'}};
      isWord(str): returns true if str is present in dictionary
                   else false.

Output:  Following words of dictionary are present
         GEEKS
         QUIZ

Method 1 : Simple Backtracking
Solution in Java

package BoggleSolver;

import java.util.ArrayList;

public class Solution {

//Define all the static words at class level

static String [] dictionary = {"GEEKS","QUIZ","GO","FOR"};

static char boggle[][]   = {{'G','I','Z'},

{'U','E','K'},

{'Q','S','E'}}; 

static int NEIGHBOURS = 8;

static int [] neighbourY = {-1,0,1,-1,1,-1, 0, 1};

static int [] neighbourX = { 1,1,1, 0,0,-1,-1,-1};

static int nrows = boggle.length;

static int ncols = boggle[0].length;

//below function will search for the word in the dictionary

static boolean findWord(StringBuilder word)

{

for(int i =0;i<dictionary.length;i++)

{

if(word.toString().compareTo(dictionary[i])==0)

{

return true;

}

}

return false;

}

//below function will search for the word characters in the neighboring cells recursively 

static StringBuilder searchWord(int row,int col,StringBuilder word,int[][] visited)

{

visited[row][col] = 1;

word.append(boggle[row][col]);

//System.out.println(word);

if(findWord(word))

{

//System.out.println(word);

return word;

}

for(int nx = row-1;nx<=row+1&&nx<nrows;nx++)

{

for(int ny = col-1;ny<=col+1&&ny<ncols;ny++)

{

if(nx>=0 && ny>=0 && visited[nx][ny]==0)

{

  StringBuilder op = searchWord(nx,ny,word,visited);

  if(op.length()>0)

  {

  return op;

  }

}

}

}

//reset the visited array col and row number to zero i.e., make it unvisited

visited[row][col] = 0;

//decrease the word length by 1

word.setLength(word.length()-1);

    return new StringBuilder();

}

//below function will check if the row and col number is valid and it is not present in visited array

static boolean isValid(int row, int col, int nx, int ny,int[][] visited)

{

if((row+nx)>-1 && (row+nx)<boggle.length && (col+ny)>-1 && (col+ny)< boggle[0].length  && visited[row+nx][col+ny]==0)

{

return true;

}

else

{

return false;

}

}

// loop through the entire boggle to find the all related words that are contained in Dictionary

static String[] findWords()

{

int [][] visited = new int[nrows][ncols];

ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();

for(int i =0;i<nrows;i++)

{

for(int j =0;j<ncols;j++)

{

StringBuilder output = searchWord(i,j,new StringBuilder(),visited);

if(output.length()>0)

{

list.add(output);

}

}

}

String[] res = null;

if(!list.isEmpty())

{

    res= new String[list.size()];

for(int i =0;i<list.size();i++)

{

res[i] = list.get(i).toString();

}

return res;

}

else

{

return null;

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

String[] res = findWords();

for(int i =0;i<res.length;i++)

{

System.out.println(res[i]);

}

}

}

Strings LeetCode – Regular Expression Matching in Java

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") return false
isMatch("aa","aa") return true
isMatch("aaa","aa") return false
isMatch("aa", "a*") return true
isMatch("aa", ".*") return true
isMatch("ab", ".*") return true
isMatch("aab", "c*a*b") return true

I had referred below link to understand the solution and implement.

Below is the solution (The only difference is i did not use the substring but used an index to traverse the string)

public static boolean patternMatch(String text,String pattern,int tIndex,int pIndex)

{

//if the pattern length is zero then condition passes if only string length is also zero 

if(pIndex>=pattern.length())

{

return tIndex == text.length();

}

if(pIndex+1==pattern.length() || pattern.charAt(pIndex+1)!='*')

{

if(tIndex>=text.length() && pattern.charAt(pIndex)!='.' &&     pattern.charAt(pIndex)!=text.charAt(tIndex))

{

return false;

}

else

{

return patternMatch(text,pattern,tIndex+1,pIndex+1);

}

}

else

{

int i = -1;

while(tIndex+i<text.length() &&  (i<0||pattern.charAt(pIndex)=='.'||pattern.charAt(pIndex)==text.charAt(tIndex+i)))

{

if(patternMatch(text, pattern, tIndex+i+1, pIndex+2))

{

return true;

}

i++;

}

}

return false;

}