Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
//Time Complexity: O(MN) where M is the number of rows and N is the number of columns. Space is O(MN).
class Data
{
int row;
int col;
int idx;
public Data(int r, int c, int i)
{
row=r;
col=c;
idx=i;
}
public int hashCode()
{
return Objects.hash(new Integer(r), new Integer(c), new Integer(idx));
}
public boolean equals(Object obj)
{
if(obj==null || !(obj instanceof Data))
{
return false;
}
Data d=(Data)obj;
return d.row==row && d.col==col && d.idx==idx;
}
}
public boolean countOccurs(String str, char[][] m)
{
if(s==null||m==null||str.length()==0||m.length==0||m[0].length==0)
{
return false;
}
int ct=0;
for(int i=0;i<m.length;i++)
{
for(int c=0;c<m[0].length;c++)
{
if(m[i][c]==str.charAt(0))
{
ct=ct+dfs(new Data(0,i,c),str,m,new HashSet<Data>());
}
}
}
return ct;
}
private int dfs(Data d,String str, int[][] mat,HashSet<Data> set)
{
if(d.idx==str.length())
{
return 1;
}
if((d.row<0||d.row==mat.length||d.col==0||d.col==mat[0].length)||(mat[d.row][d.col]!=str.charAt(d.idx))||set.containsKey(d))
{
return 0;
}
int[] r={-1,0,1};
int[] c={-1,0,1};
int ct=0;
for(int i=0;i<r.length;i++)
{
for(int i=0;i<c.length;i++)
{
if(i!=d.row || c!=d.col)
{
ct=ct+dfs(new Data(d.idx+1,d.row+r[i],d.col+c[i]),str,mat,set);
}
}
}
if(ct==0)
{
set.put(d);
}
return ct;
}
public class FindString { public static void main(String[] args) { System.out.println("Inside Main ");
String b = "AMAZON";
int len = b.length() - 1;
char[][] a = { {'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'A', 'M', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'} };
int k = 0;
char[] val = b.toCharArray();
char[] val1 = new char[len + 1];
char[] val2 = new char[len + 1];
char[] val3 = new char[len + 1];
char[] val4 = new char[len + 1];
for (int i = 0; i <= len; i++) { System.out.println("Value of i " + i);
Boolean val1bool = true;
Boolean val2bool = true;
Boolean val3bool = true;
Boolean val4bool = true;
for (int j = 0; j <= len; j++) { System.out.println("Value of i :" + i + " j: " + j + " value : " + a[i][j]);
val1[i] = a[i][j];
if ((val[j] == a[i][j]) && val1bool) {
val1bool = true;
if (j == len)
k++; } else {
val1bool = false; }
System.out.println("Value of i :" + (i) + " j: " + (len - j) + " value : " + a[i][len - j]);
val2[i] = a[i][len - j];
if ((val[j] == a[i][len - j]) && val2bool) { val2bool = true;
if (j == len)
k++; } else {
val2bool = false; }
System.out.println("Value of i :" + (j) + " j: " + (i) + " value : " + a[j][i]);
if ((val[j] == a[j][i]) && val3bool) { val3bool = true;
if (j == len)
k++; } else {
val3bool = false; }
System.out.println("Value of i :" + (len - j) + " j: " + (i) + " value : " + a[len - j][i]);
if ((val[j] == a[len - j][i]) && val4bool) {
val4bool = true;
if (j == len) {k++;}} else {
val4bool = false; } }
System.out.println("Value of K " + k);
}}}
public static int numStrings(char[][] c, String s) {
int count = 0;
if (!s.isEmpty()) {
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c[i].length; j++) {
if (c[i][j] == s.charAt(0)) {
count += helper(c, s, i, j);
}
}
}
}
return count;
}
public static int helper(char[][] c, String s, int i, int j) {
if (s.length() == 1) {
return 1;
} else {
int count = 0;
String s2 = s.substring(1, s.length());
char current = s2.charAt(0);
// Check top character
if (i > 0 && c[i-1][j] == current) {
count += helper(c, s2, i-1, j);
}
// Check bottom character
if (i < c.length - 1 && c[i+1][j] == current) {
count += helper(c, s2, i+1, j);
}
// Check right character
if (j < c[i].length - 1 && c[i][j+1] == current) {
count += helper(c, s2, i, j+1);
}
// Check left character
if (j > 0 && c[i][j-1] == current) {
count += helper(c, s2, i, j-1);
}
return count;
}
}
First of all pseudo code:
create array of characters AMAZON as amazonCharArray
iterate matrix from left-right top-bottom.
if you find first char of amazonCharArray then
Iterate through amazonCharArray, look for next character of amazonCharArray at c+1,c-1,r+1,r-1 position. If found continue oherwise break
if all chars are found increment stringCount by 1.
NOTE :
Here is the actual code:
public class IdentifyString {
//private static boolean[][] boolArray=new boolean[6][6];
private static int stringCount=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] inputArray = { {'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'A', 'M', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'} };
countOccurence(inputArray,"AMAZON",0,0);
System.out.println("count of string is "+stringCount);
}
public static void countOccurence(char[][] inputArray, String inputString,int startRow,int startCol){
String prevUsed;
int c=startCol;
boolean colsIteratedOnce=false;
boolean breakLoop=false;
//create array of characters AMAZON as amazonCharArray
char[] amazonCharArray=inputString.toCharArray();
//iterate matrix from left-right top-bottom.
outermost:for(int r=startRow;r<inputArray.length;r++){
if(colsIteratedOnce){
c=0;
}
colsIteratedOnce=true;
for(; c<inputArray[r].length; c++){
//if you find first char of amazonCharArray then
if(inputArray[r][c]==amazonCharArray[0]){
prevUsed="";
if(c+1<inputArray[r].length){
startRow=r;
startCol=c+1;
}else if(r+1<inputArray.length){
startRow=r+1;
startCol=0;
}else{
breakLoop=true;
}
//Iterate through amazonCharArray, look for next character of amazonCharArray at c+1,c-1,r+1,r-1 position.
//If found continue otherwise break
for(int i=1; i<amazonCharArray.length;i++){
if(r+1<inputArray.length && amazonCharArray[i]==inputArray[r+1][c] && prevUsed!=null && !"r-1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
r=r+1;
prevUsed="r+1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
if(r-1>=0 && amazonCharArray[i]==inputArray[r-1][c] && prevUsed!=null && !"r+1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
r=r-1;
prevUsed="r-1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
if(c+1<inputArray[r].length && amazonCharArray[i]==inputArray[r][c+1] && prevUsed!=null && !"c-1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
c=c+1;
prevUsed="c+1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
if(c-1>=0 && amazonCharArray[i]==inputArray[r][c-1] && prevUsed!=null && !"c+1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
c=c-1;
prevUsed="c-1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
r=startRow;
c=startCol;
break;
}
}
}
}
}
}
package com.test.staticthread;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
public class CountAmazonInTwoDArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] arr = {{'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'}, {'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'B', 'B', 'A'}, {'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'}};
HashMap<Character, Integer> hm = new HashMap<>();
ArrayList<Character> arrayList = new ArrayList<>();
String s = "AMAZON";
for (char ch : s.toCharArray())
arrayList.add(ch);
int rows = arr.length;
int colums = arr[0].length;
for (int j = 0; j < rows; j++) {
for (int k = 0; k < colums; k++) {
char ch = arr[j][k];
if (arrayList.contains(ch)) {
if (hm.containsKey(ch)) {
hm.put(ch, hm.get(ch) + 1);
} else {
hm.put(ch, 1);
}
}
}
}
//what we are doing is trying to sort the list entry object by frequency of given charcter in 2 d array.
//limiting factor in creating string will be one with lowest number of charcters/
List<Entry<Character, Integer>> list = new ArrayList<>(
hm.entrySet());
Collections.sort(list, new Comparator<Entry<Character, Integer>>() {
@Override
public int compare(Entry<Character, Integer> o1,
Entry<Character, Integer> o2) {
// TODO Auto-generated method stub
return o1.getValue() - o2.getValue();
}
});
Entry<Character, Integer> entry1 = list.get(0);
if (entry1.getKey() == 'A') {
if (entry1.getValue() % 2 != 0) {
System.out.println(entry1.getValue() - 1);
}
else {
System.out.println(entry1.getValue() / 2);
}
} else {
System.out.println(entry1.getValue());
}
}
}
public class IdentifyString {
//private static boolean[][] boolArray=new boolean[6][6];
private static int stringCount=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] inputArray = { {'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'A', 'M', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'} };
countOccurence(inputArray,"AMAZON",0,0);
System.out.println("count of string is "+stringCount);
}
public static void countOccurence(char[][] inputArray, String inputString,int startRow,int startCol){
String prevUsed;
int c=startCol;
boolean colsIteratedOnce=false;
boolean breakLoop=false;
//create array of characters AMAZON as amazonCharArray
char[] amazonCharArray=inputString.toCharArray();
//iterate matrix from left-right top-bottom.
outermost:for(int r=startRow;r<inputArray.length;r++){
if(colsIteratedOnce){
c=0;
}
colsIteratedOnce=true;
for(; c<inputArray[r].length; c++){
//if you find first char of amazonCharArray then
if(inputArray[r][c]==amazonCharArray[0]){
prevUsed="";
if(c+1<inputArray[r].length){
startRow=r;
startCol=c+1;
}else if(r+1<inputArray.length){
startRow=r+1;
startCol=0;
}else{
breakLoop=true;
}
//Iterate through amazonCharArray, look for next character of amazonCharArray at c+1,c-1,r+1,r-1 position.
//If found continue otherwise break
for(int i=1; i<amazonCharArray.length;i++){
if(r+1<inputArray.length && amazonCharArray[i]==inputArray[r+1][c] && prevUsed!=null && !"r-1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
r=r+1;
prevUsed="r+1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
if(r-1>=0 && amazonCharArray[i]==inputArray[r-1][c] && prevUsed!=null && !"r+1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
r=r-1;
prevUsed="r-1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
if(c+1<inputArray[r].length && amazonCharArray[i]==inputArray[r][c+1] && prevUsed!=null && !"c-1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
c=c+1;
prevUsed="c+1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
if(c-1>=0 && amazonCharArray[i]==inputArray[r][c-1] && prevUsed!=null && !"c+1".equals(prevUsed)){
if(i!=amazonCharArray.length-1){
c=c-1;
prevUsed="c-1";
continue;
}else{
//if all chars are found increment stringCount by 1.
stringCount=stringCount+1;
if(!breakLoop)
countOccurence(inputArray,inputString,startRow,startCol);
break outermost;
}
}
r=startRow;
c=startCol;
break;
}
}
}
}
}
}
In question, it has asked for getting the total number of AMAZON string from the array. So the best way is store the string in a map [need to handle the duplicate char also], iterate through the 2D array and update the count of chars in map [if present]. Finally check the smallest number from the map [need to some extra calculation for duplicate numbers], can print as the output.
Time complexity for the alg is O(n+m)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
int search_internal(char *needle, int row, int col, char **hay, int row_max, int col_max)
{
int found = 0;
if (row >= 0 && row <= row_max
&& col >= 0 && col <= col_max
&& *needle == hay[row][col]) {
char match = *needle++;
hay[row][col] = 0;
if (*needle == 0) {
found = 1;
} else {
found += search_internal(needle, row, col+1, hay, row_max, col_max);
found += search_internal(needle, row, col-1, hay, row_max, col_max);
found += search_internal(needle, row+1, col, hay, row_max, col_max);
found += search_internal(needle, row-1, col, hay, row_max, col_max);
}
hay[row][col] = match;
}
return found;
}
int search(char *needle, int row, int col, char **hay, int row_count, int col_count)
{
int found = 0;
int r, c;
for (r = 0; r < row_count; ++r) {
for (c = 0; c < col_count; ++c) {
found += search_internal(needle, r, c, hay, row_count - 1, col_count - 1);
}
}
return found;
}
int main()
{
char needle[] = "AMAZON";
char *input[] = {
"BBABBN",
"BBMBBO",
"BBABBZ",
"NOZBBA",
"BBBBBM",
"BBBBBA"
};
char *hay[ARRAY_SIZE(input)];
int i;
for (i = 0; i < ARRAY_SIZE(input); ++i) {
hay[i] = malloc(strlen(input[i]));
strcpy(hay[i], input[i]);
}
printf("count: %d\n", search(needle, 0, 0, hay, ARRAY_SIZE(hay), strlen(hay[0])));
return 0;
}
The Die ordered me to learn Python. So I am trying.
def count(the_string, the_array) :
string_dict = dict.fromkeys(list(the_string), 0)
count_dict= dict.copy(string_dict)
for c in list(the_string) :
string_dict[c] = string_dict[c] + 1
for row in the_array:
for l in row:
if l in count_dict :
count_dict[l] = count_dict[l] + 1
for letter in count_dict :
count_dict[letter] = int(count_dict[letter]/string_dict[letter])
counter = min(count_dict.values() )
print(counter)
count('abba', [['a', 'b', 'b', 'a'], ['c','a', 'b', 'd'], ['b', 'a', 'a', 'a'], ['a', 'b', 'b', 'a'] ])
def count(the_string, the_array) :
string_dict = dict.fromkeys(list(the_string), 0)
count_dict= dict.copy(string_dict)
for c in list(the_string) :
string_dict[c] = string_dict[c] + 1
for row in the_array:
for l in row:
if l in count_dict :
count_dict[l] = count_dict[l] + 1
for letter in count_dict :
count_dict[letter] = int(count_dict[letter]/string_dict[letter])
counter = min(count_dict.values() )
print(counter)
#example
count('abba', [['a', 'b', 'b', 'a'], ['c','a', 'b', 'd'], ['b', 'a', 'a', 'a'], ['a', 'b', 'b', 'a'] ])
def count(the_string, the_array) :
string_dict = dict.fromkeys(list(the_string), 0)
count_dict= dict.copy(string_dict)
for c in list(the_string) :
string_dict[c] = string_dict[c] + 1
for row in the_array:
for l in row:
if l in count_dict :
count_dict[l] = count_dict[l] + 1
for letter in count_dict :
count_dict[letter] = int(count_dict[letter]/string_dict[letter])
counter = min(count_dict.values() )
print(counter)
#example
count('abba', [['a', 'b', 'b', 'a'], ['c','a', 'b', 'd'], ['b', 'a', 'a', 'a'], ['a', 'b', 'b', 'a'] ])
def count(the_string, the_array) :
if len(the_string) == 0 :
return 0
elif len(the_array) == 0 :
return 0
#Store in a map the freq of each character in
# input string
string_dict = dict.fromkeys(list(the_string), 0)
for c in list(the_string) :
string_dict[c] = string_dict[c] + 1
#store in a map the number each character of input string
#occurs in input array
freq_dict = dict.fromkeys(list(the_string), 0)
for row in the_array:
for l in row:
if l in freq_dict :
freq_dict[l] = freq_dict[l] + 1
# update the map values
# dividing the number of occurencies in input array
# by the number of times the same character occurs
# in input string. Now the minimum value equals
# the number of times input string appears in input array
for letter in freq_dict :
freq_dict[letter] = int(freq_dict[letter]/string_dict[letter])
return min(freq_dict.values() )
#example
input_array = [
['B', 'B', 'A', 'B', 'B', 'N'],
['B', 'B', 'M', 'B', 'B', 'O'],
['B', 'B', 'A', 'B', 'B', 'Z'],
['N', 'O', 'Z', 'B', 'B', 'A'],
['B', 'B', 'B', 'B', 'B', 'M'],
['B', 'B', 'B', 'B', 'B', 'A']
]
input_string = 'AMAZON'
counter = count(input_string, input_array)
for row in input_array :
print(row)
print('The string %s appears %s times' % (input_string, counter))
public static void main(String[] args) {
char[][] a = {
{'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'B', 'B', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'}
};
String str = "AMAZON";
System.out.println(getStringCount(a,str,6,6));
}
public static class Neighbour {
char c;
int i;
int j;
Neighbour(char ch,int m,int n) {
c = ch;
i = m;
j = n;
}
}
public static final int MATRIX_ELEMENTS = 36;
private static int getStringCount(char[][] a, String str,int R,int C) {
int count = 0;
int k=0;
int neighI;
int neighJ;
char u = 0;
char[] input = str.toCharArray();
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
if(k < input.length && a[i][j] == input[k]) {
u = a[i][j];
k++;
neighI = i;
neighJ = j;
while(u != 0) {
Neighbour neighbour = getMatchingNeighbour(a,input,u,neighI,neighJ,k,R,C);
if(neighbour == null)
break;
k++;
u = neighbour.c;
neighI = neighbour.i;
neighJ = neighbour.j;
if(k == str.length()) {
count++;
k=0;
break;
}
}
}
}
}
return count;
}
private static Neighbour getMatchingNeighbour(char[][] a,char[] input,char u, int i, int j,int k,int R,int C) {
int iPlusOne = i+1;
int iMinusOne = i-1;
int jPlusOne = j+1;
int jMinusOne = j-1;
boolean inpuutIndex = k < input.length ? true : false;
if(iPlusOne < R && inpuutIndex && (a[iPlusOne][j] == input[k]))
return new Neighbour(input[k],iPlusOne,j);
if(iMinusOne >= 0 && inpuutIndex && (a[iMinusOne][j] == input[k]))
return new Neighbour(input[k],iMinusOne,j);
if(jPlusOne < C && inpuutIndex && (a[i][jPlusOne] == input[k]))
return new Neighbour(input[k],i,jPlusOne);
if(jMinusOne >= 0 && inpuutIndex && (a[i][jMinusOne] == input[k]))
return new Neighbour(input[k],i,jMinusOne);
return null;
}
public static void main(String[] args) {
char[][] a = {
{'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'B', 'B', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'}
};
String str = "AMAZON";
System.out.println(getStringCount(a,str,6,6));
}
public static class Neighbour {
char c;
int i;
int j;
Neighbour(char ch,int m,int n) {
c = ch;
i = m;
j = n;
}
}
public static final int MATRIX_ELEMENTS = 36;
private static int getStringCount(char[][] a, String str,int R,int C) {
int count = 0;
int k=0;
int neighI;
int neighJ;
char u = 0;
char[] input = str.toCharArray();
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
if(k < input.length && a[i][j] == input[k]) {
u = a[i][j];
k++;
neighI = i;
neighJ = j;
while(u != 0) {
Neighbour neighbour = getMatchingNeighbour(a,input,u,neighI,neighJ,k,R,C);
if(neighbour == null)
break;
k++;
u = neighbour.c;
neighI = neighbour.i;
neighJ = neighbour.j;
if(k == str.length()) {
count++;
k=0;
break;
}
}
}
}
}
return count;
}
private static Neighbour getMatchingNeighbour(char[][] a,char[] input,char u, int i, int j,int k,int R,int C) {
int iPlusOne = i+1;
int iMinusOne = i-1;
int jPlusOne = j+1;
int jMinusOne = j-1;
boolean inpuutIndex = k < input.length ? true : false;
if(iPlusOne < R && inpuutIndex && (a[iPlusOne][j] == input[k]))
return new Neighbour(input[k],iPlusOne,j);
if(iMinusOne >= 0 && inpuutIndex && (a[iMinusOne][j] == input[k]))
return new Neighbour(input[k],iMinusOne,j);
if(jPlusOne < C && inpuutIndex && (a[i][jPlusOne] == input[k]))
return new Neighbour(input[k],i,jPlusOne);
if(jMinusOne >= 0 && inpuutIndex && (a[i][jMinusOne] == input[k]))
return new Neighbour(input[k],i,jMinusOne);
return null;
}
public class Counter {
public static void main(String[] args) {
char[][] a = {
{'B','B','A','B','B','N'},
{'B','B','M','B','B','O'},
{'B','B','A','B','B','Z'},
{'N','O','Z','B','B','A'},
{'B','B','B','B','B','M'},
{'B','B','B','B','B','A'}
};
int count = 0;
for( int i = 0; i < a.length; i++) {
for ( int j = 0; j < a[0].length; j++) {
count += wordCount("AMAZON", a, 0, i, j, 0);
}
}
System.out.println(count);
}
private static int wordCount(String word, char[][] a,int stringIndex, int currentRow, int currentCol, int lastDir) {
if (currentRow < 0 || currentRow > a.length - 1 || currentCol < 0 || currentCol > a[0].length - 1) {
return 0;
}
if (a[currentRow][currentCol] != word.charAt(stringIndex)) {
return 0;
}
else if (stringIndex == word.length() - 1) {
return 1;
}
else {
int count = 0;
if (lastDir != 2) {
count += wordCount(word, a, stringIndex + 1, currentRow, currentCol - 1, 1);
}
if (lastDir != 1) {
count += wordCount(word, a, stringIndex + 1, currentRow, currentCol + 1, 2);
}
if (lastDir != 4) {
count += wordCount(word, a, stringIndex + 1, currentRow - 1, currentCol, 3);
}
if (lastDir != 3) {
count += wordCount(word, a, stringIndex + 1, currentRow + 1, currentCol, 4);
}
return count;
}
}
}
Here is a working solution using a Hash Table and recursion.
import java.util.HashMap;
public class InterLeave {
static String inp = "AMAZON";
static char[][] a = { {'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'B', 'B', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'} };
static HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
static int counter = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 0;
for(int i=0; i<a[0].length; i++){
resetHash();
for(int j=0; j<a[0].length; j++){
if(hash.containsKey(a[i][j]) && hash.get(a[i][j]) > 0){
count+=findCount(i, j);
//hash.put(a[i][j], hash.get(a[i][j]) - 1);
//a[i][j]=0;
}
}
}
System.out.println(count);
for(int i=0; i < a[0].length; i++ ){
for(int j=0; j < a[0].length; j++){
System.out.print(a[i][j]);
}
System.out.println();
}
}
static int findCount(int i, int j){
int found = 0;
boolean nonZero = false;
for(int val : hash.values()){
//System.out.print(val);
if(val > 0){
nonZero = true;
break;
}
}
//System.out.println();
if(!nonZero && counter == inp.length()){
//System.out.println("Hello");
counter = 0;
return 1;
}
if(i< 0 || j <0 || i>=a[0].length || j >= a[0].length){
return found;
}
if(hash.containsKey(a[i][j]) && hash.get(a[i][j]) > 0){
hash.put(a[i][j], hash.get(a[i][j]) - 1);
a[i][j]=0;
counter++;
found+=findCount(i+1, j)+findCount(i,j+1)+findCount(i-1, j)+ findCount(i, j-1);
}
return found;
}
static void resetHash(){
for(int i =0; i< inp.length(); i++){
char val = inp.charAt(i);
if(hash.containsKey(val)){
hash.put(val, hash.get(val)+1);
}
else{
hash.put(val,1);
}
}
}
}
- cva dasan July 21, 2016#include <stdio.h> #include <string.h> #include <stdlib.h> #define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a)) int search_internal(char *needle, int row, int col, char **hay, int row_max, int col_max) { int found = 0; if (row >= 0 && row <= row_max && col >= 0 && col <= col_max && *needle == hay[row][col]) { char match = *needle++; hay[row][col] = 0; if (*needle == 0) { found = 1; } else { found += search_internal(needle, row, col+1, hay, row_max, col_max); found += search_internal(needle, row, col-1, hay, row_max, col_max); found += search_internal(needle, row+1, col, hay, row_max, col_max); found += search_internal(needle, row-1, col, hay, row_max, col_max); } hay[row][col] = match; } return found; } int search(char *needle, int row, int col, char **hay, int row_count, int col_count) { int found = 0; int r, c; for (r = 0; r < row_count; ++r) { for (c = 0; c < col_count; ++c) { found += search_internal(needle, r, c, hay, row_count - 1, col_count - 1); } } return found; } int main() { char needle[] = "AMAZON"; char *input[] = { "BBABBN", "BBMBBO", "BBABBZ", "NOZBBA", "BBBBBM", "BBBBBA" }; char *hay[ARRAY_SIZE(input)]; int i; for (i = 0; i < ARRAY_SIZE(input); ++i) { hay[i] = malloc(strlen(input[i])); strcpy(hay[i], input[i]); } printf("count: %d\n", search(needle, 0, 0, hay, ARRAY_SIZE(hay), strlen(hay[0]))); return 0; }