Google Interview Question
Software Engineer / DevelopersCountry: Australia
Interview Type: Phone Interview
I think, your analysis is nice, but I am pretty sure you cannot replace O(m*n*2^k ) by simply O(2^k) since. By definition, then you must be able find some constant c such that c*2^k > m*n*2^k for all n,m,k. But this is not possible since n and m are parameters that may scale up to infinity. Unless you state explicitly the correlation between k,m,n, you should not better make this kind of simplifications...
//How many occurrences of a given search word can you find in a two-dimensional
// array of characters given that the word can go up, down, left, right,
//and around 90 degree bends?
//Ex:
//Count of occurrences of SNAKES
//S N B S N
//B A K E A
//B K B B K
//S E B S E
//The answer is 3.
#include<iostream>
#include<stdlib.h>
using namespace std;
//Maximum movement allowed is equal to length of target word
int FoundWaysToMakeWord(int arr[][5],int i, int j,int m, int n,int index, int maxIndex,int curr[], int target[])
{
if(i == -1 || i == m) //allowed index are upto m-1
{
return 0;
}
if(j == -1 || j == n)//allowed index are upto n-1
{
return 0;
}
if(index > maxIndex)//SNAKE max index = 4 we can fill char 0 1 2 3 4 position
{
return 0;
}
curr[index] = arr[i][j];
if(curr[index] != target[index])
{
return 0;//char mismatch found
}
if(index == maxIndex)//it mean last char also matched mean we done it
{
return 1;
}
return (FoundWaysToMakeWord(arr,i+1,j,m,n,index+1,maxIndex,curr,target) +
FoundWaysToMakeWord(arr,i-1,j,m,n,index+1,maxIndex,curr,target) +
FoundWaysToMakeWord(arr,i,j+1,m,n,index+1,maxIndex,curr,target) +
FoundWaysToMakeWord(arr,i,j-1,m,n,index+1,maxIndex,curr,target));
}
/*
//start point can be only (0,0),(m-1,0),(0,n-1),(m-1,n-1)
int FoundWaysToMakeWordUtil(int arr[][5],int target[], int m, int n,int length)
{
int *p = new int[length];
return FoundWaysToMakeWord(arr,0,0,m,n,0,length-1,p,target)+
FoundWaysToMakeWord(arr,0,n-1,m,n,0,length-1,p,target)+
FoundWaysToMakeWord(arr,m-1,n-1,m,n,0,length-1,p,target)+
FoundWaysToMakeWord(arr,m-1,0,m,n,0,length-1,p,target);
}
*/
int FoundWaysToMakeWordUtil(int arr[][5],int target[], int m, int n,int length)
{
int *p = new int[length];
int count = 0;
for(int i = 0; i < m;i++)
{
for(int j = 0; j < n; j++)
{
if(arr[i][j] == 'S')
{
count += FoundWaysToMakeWord(arr,i,j,m,n,0,length-1,p,target);
}
}
}
return count;
}
int main()
{
int p[4][5] = {
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};
int target[] = {'S','N','A','K','E','\0'};
cout<<FoundWaysToMakeWordUtil(p,target,4,5,5)<<endl;
}
I believe this solution doesn't work for search words that are palindromes.
Say You were searching for the word "SNAANS", and your 2D array looked
like this
SNA---
______
______
I believe your solution would find one path. This is because you are searching in
all directions regardless of the direction from which you came. If you are moving
RIGHT, you only want to move either RIGHT, UP, or DOWN, not LEFT. The case
for other directions is similar, you don't want to go back in the opposite direction.
Also, You should consider adding a table to store whether you can make the search word from a given index in p, if you were led to your index in p by a specific direction, and have seen particular number of correct characters so far. So
your map would be keyed like so
map[cur_row][cur_col][direction][curr_index]
This would greatly speed up the algorithm I believe, since you don't solve the same subproblems again.
Consider a 2D array like this
SSSSSS
SN
NAKES
There are 2 paths here
- -S
S and -N
NAKES -AKES
If you used a map as I said, once you found one of these paths, you
would store in the index corresponding to the K position that you found the string when you were heading to the LEFT and were at index 3, so once you got to
that index and checked the map, you would see a 1 stored there, and would just be able to return 1 right then and there. In this example the map is obviously not
going to give you much of a benefit, but consider if the search words were a lot
longer and you had a lot of cases of solving the same sub problems.
I jus want to give a brief explanation about this question since all the others just posted their code. The basic idea is to do search at each possible possition. In this example, we want to find "SNAKE", then the possible start positions are the positions where the character is "S", then you keep a visited array to avoid going back to the same position. The visited array is a little bit tricky. For example, if the matrix is :
S N B S N
B A K E A
B K B B K
S E B S E
Then you go from (0, 0) to (1, 0), to (2, 0), you visited array in these three positions are set as true, but when you discovered that (2, 0) is not a possible answer, you should reset the visited array at position (2, 0) to false immediately since you may go to it later.
#include<iostream>
using namespace std;
void RecursiveCount(int X, int Y, int Xhigh, int Yhigh, int it, char Search[7], int length,char Word[4][6], int *Count)
{
char c = Word[X][Y];
if( c == Search[it])
{
//cout<<X<<"--"<<Y<<"--it:"<<it<<"--length:"<<length<<endl;
if( it == length-1)
{
(*Count)++;
}
else if(it < length-1)
{
if(X-1 > -1) RecursiveCount(X-1,Y,Xhigh,Yhigh, it+1,Search,length,Word,Count);
if(X+1 < Xhigh) RecursiveCount(X+1,Y,Xhigh,Yhigh, it+1,Search,length,Word,Count);
if(Y-1 > -1) RecursiveCount(X,Y-1,Xhigh,Yhigh, it+1,Search,length,Word,Count);
if(Y+1 < Xhigh) RecursiveCount(X,Y+1,Xhigh,Yhigh, it+1,Search,length,Word,Count);
}
}
}
int main()
{
char Word[4][6] = {"SNBSN","BAKEA","BKBBK","SEBSE"};
char Search[7] = {"SNAKES"};
int length = 6;
int Count = 0;
for(int i=0;i<4;i++)
{
for(int j=0;j<5;j++)
{
if(Word[i][j] == Search[i]) RecursiveCount(i,j,5,5,0,Search,length,Word,&Count);
}
}
cout<<"No.of Occurences for the Search Word ="<<Count<<endl;
getchar();
return 0;
}
Confirmed working Java solution below. You also have to keep track of which nodes you've visited so far.
import java.util.ArrayList;
public class Boggle {
private static class Position {
public int row;
public int col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}
public boolean equals(Object o) {
if (!(o instanceof Position)) return false;
Position other = (Position) o;
return (this.row == other.row) && (this.col == other.col);
}
public String toString() {
return "(" + row + "," + col + ")";
}
}
public static int wordCount(char[][] grid, String word) {
int count = 0;
Position p = new Position(0, 0);
ArrayList<Position> visited;
for (int row = 0; row < grid.length; row++) {
p.row = row;
for (int col = 0; col < grid[0].length; col++) {
p.col = col;
visited = new ArrayList<Position>();
count += wordCountHelper(grid, word, p, visited);
}
}
return count;
}
// number of rows = grid.length
// number of cols = grid[0].length
// returns the # of times we can find the word word starting at position p in the grid
public static int wordCountHelper(char[][] grid, String word, Position p, ArrayList<Position> visited) {
if (word.charAt(0) != grid[p.row][p.col]) return 0;
// if p is in the list visited, then return 0;
for (Position visited_pos : visited) {
if (p.equals(visited_pos)) return 0;
}
visited.add(p);
if (word.length() == 1) {
System.out.println(visited);
return 1; // word.charAt(0) == grid[p.row][p.col]
}
int count = 0;
int n_visited = visited.size();
// check up
if (p.row != 0) {
Position p_next = new Position(p.row - 1, p.col);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}
// check down
if (p.row != grid.length - 1) {
Position p_next = new Position(p.row + 1, p.col);
keepFirstKPositions(visited, n_visited);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}
// check left
if (p.col != 0) {
Position p_next = new Position(p.row, p.col - 1);
keepFirstKPositions(visited, n_visited);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}
// check right
if (p.col != grid[0].length - 1) {
Position p_next = new Position(p.row, p.col + 1);
keepFirstKPositions(visited, n_visited);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}
return count;
}
public static void keepFirstKPositions(ArrayList<Position> list, int k) {
int size = list.size();
if (k >= size) return;
for (int i = 0; i < size - k; i++) {
int idx = size - 1 - i;
list.remove(idx);
}
}
public static void main(String[] args) {
char[][] grid = {
{'s', 'n', 'b', 's', 'n'},
{'b', 'a', 'k', 'e', 'a'},
{'b', 'k', 'b', 'b', 'k'},
{'s', 'e', 'b', 's', 'e'}
};
String word = "snakes";
System.out.println("The word " + word + " appears " + wordCount(grid, word) + " times.");
}
}
/*
* we need prevRow and preCol to stop going in the route we came from
*/
public static int findOccurence(char[][] a, int row, int col, String text,
int textIndex, int prevRow, int prevCol) {
//base condition
if (row < 0 || col < 0 || row >= a.length || col >= a[row].length)
return 0;
if (a[row][col] == text.charAt(textIndex) && textIndex == text.length()-1)
return 1;
int retValue = 0;
//if character matches then try to match next character by incrementing textIndex
if (a[row][col] == text.charAt(textIndex)) {
if (prevRow != row + 1 || prevCol != col)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row + 1, col, text, textIndex + 1, row, col);
if (prevRow != row || prevCol != col + 1)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row, col + 1, text, textIndex + 1,row, col);
if (prevRow != row - 1 || prevCol != col)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row - 1, col, text, textIndex + 1,row, col);
if (prevRow != row || prevCol != col - 1)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row, col - 1, text, textIndex + 1,row, col);
}
return retValue;
}
public static void main(String[] args) {
char[][] a = { { 'S', 'N', 'B', 'S', 'N' },
{ 'B', 'A', 'K', 'E', 'A' },
{ 'B', 'K', 'B', 'B', 'K' },
{ 'S', 'E', 'B', 'S', 'E' } };
String str = "SNAKES";
int result = 0;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++)
result += findOccurence(a, i, j, str, 0, -1, -1);
}
System.out.println(result);
}
}
/**
* Time complexity: O(N^3)
* Space complexity: O(1)
*/
import java.util.ArrayList;
import java.util.List;
public class FindOccurences
{
private int count;
private boolean[][] visited;
private int[] dx = {0,0 ,1, -1};
private int[] dy = {1,-1,0,0 };
private String key;
private char[][] input;
private int rowCount;
private int colCount;
class Location
{
int x;
int y;
Location(int x, int y)
{
this.x = x;
this.y = y;
}
}
public int find(char[][] input, String key)
{
List<Location> locationList = findLocations(input, key.charAt(0));
visited = new boolean[input.length][input[0].length];
this.input = input;
this.key = key;
this.rowCount = input.length;
this.colCount = input[0].length;
for(Location loc : locationList)
{
List<Character> list = new ArrayList<Character>();
list.add(key.charAt(0));
search(loc.x, loc.y, list, 0);
}
return count;
}
private void search(int x, int y, List<Character> arrayList, int index)
{
if (index == this.key.length()-1)
{
StringBuffer sb = new StringBuffer();
for(int i = 0 ; i < arrayList.size() ; i++)
{
sb.append(arrayList.get(i));
}
if (sb.toString().intern().equals(this.key))
{
count++;
}
return;
}
else
{
if (arrayList.get(arrayList.size()-1) != this.key.charAt(index))
{
return;
}
}
for(int i = 0 ; i < 4 ; i++)
{
if (valid(x+dx[i], y+dy[i]))
{
arrayList.add(input[x+dx[i]][y+dy[i]]);
visited[x+dx[i]][y+dy[i]] = true;
search(x+dx[i], y+dy[i], arrayList, index+1);
visited[x+dx[i]][y+dy[i]] = false;
arrayList.remove(arrayList.size()-1);
}
}
}
private boolean valid(int i, int j)
{
return (i>= 0 && i < rowCount && j >=0 && j < colCount && visited[i][j] == false);
}
private List<Location> findLocations(char[][] input, char key)
{
List<Location> retVal = new ArrayList<Location>();
for(int i = 0 ; i < input.length ; i++)
{
for(int j = 0 ; j < input[0].length ; j++)
{
if (input[i][j] == key)
{
retVal.add(new Location(i,j));
}
}
}
return retVal;
}
/**
* @param args
*/
public static void main(String[] args)
{
char[][] a = { { 'S', 'N', 'B', 'S', 'N' },
{ 'B', 'A', 'K', 'E', 'A' },
{ 'B', 'K', 'B', 'B', 'K' },
{ 'S', 'E', 'B', 'S', 'E' } };
String str = "SNAKES";
int result = new FindOccurences().find(a, str);
System.out.println(result);
}
}
Here is the code in C :)
#include <stdio.h>
#include <conio.h>
#include <string.h>
int row=4,col=5;
int occur(char a[][5],int x,int y,char targ[],int index,int n)
{
if(x<0||y<0||x>=row||y>=col)
return 0;
if(index>n)
return 0;
if(a[x][y]!=targ[index])
{
return 0;
}
if(index==strlen(targ)-1)
{
return 1;
}
return (occur(a,x,y+1,targ,index+1,n)
+occur(a,x+1,y,targ,index+1,n)
+occur(a,x-1,y,targ,index+1,n)
+occur(a,x,y-1,targ,index+1,n));
}
int count(char a[][5],char targ[])
{
int d=0;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(a[i][j]=='S')
d+=occur(a,i,j,targ,0,strlen(targ)-1);
}
}
return d;
}
int main()
{
char a[][5]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
char c[]={"SNAKES"};
printf("No of occurences are %d ",count(a,c));
}
#include "stdafx.h"
#include <iostream>
using namespace std;
int moveAndCheckRemainingString(char a[][5],char* c, int starttingIndex , int length, int i , int j, int arrayH, int Dir);
bool isMoveValid(int i, int j , int arrayH, int arrayL);
bool isRightBan(int Dir);
bool isLeftBan(int Dir);
bool isUpBan(int Dir);
bool isDownBan(int Dir);
int main()
{
char a[][5]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
char c[]={"SNAKES"};
int i = 0;
int j = 0;
int occurance = 0;
for(;i< 4 ; i++)
for(; j< 5 ; j++)
{
if(a[i][j] == 'S')
{
occurance += moveAndCheckRemainingString(a, c, 1, 6, i, j, 4 ,-1);
}
}
cout << "occurance : " << occurance;
return 0;
}
int moveAndCheckRemainingString(char a[][5],char* c, int starttingIndex , int length, int i , int j, int arrayH, int Dir)
{
int occ = 0;
if(starttingIndex == length-1)
{
return 1;
}
// check right move
if(isMoveValid(i, j+1, arrayH, 5) && !isRightBan(Dir) && a[i][j+1] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i, j+1, arrayH, 2);
}
// check left
if(isMoveValid(i, j-1, arrayH, 5) && !isLeftBan(Dir) && a[i][j-1] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i, j+1, arrayH, 1);
}
// check Up
if(isMoveValid(i+1, j, arrayH, 5) && !isUpBan(Dir) && a[i+1][j] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i+1, j, arrayH, 3);
}
// Check down
if(isMoveValid(i, j-1, arrayH, 5) && !isDownBan(Dir) &&a[i-1][j] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i-1, j, arrayH, 4);
}
return occ;
}
bool isMoveValid(int i, int j , int arrayH, int arrayL)
{
return (i<arrayH) && (j < arrayL);
}
// 1 = left
// 2 = right
// 3 = up
// 4 = down
bool isRightBan(int Dir)
{
if(Dir == 1)
{
return true;
}
return false;
}
bool isLeftBan(int Dir)
{
if(Dir == 2)
{
return true;
}
return false;
}
bool isUpBan(int Dir)
{
if(Dir == 4)
{
return true;
}
return false;
}
bool isDownBan(int Dir)
{
if(Dir == 3)
{
return true;
}
return false;
}
#include<stdio.h>
#include<string.h>
int count,len;
char a[100][100],s[50],cc;
int m,n;
int vis[100][100];
int see;
void dfs(int i,int j){
vis[i][j]=1;
if(see==len){
count++;
return;
}
if(i-1>=0 && j>=0){
if(s[see]==a[i-1][j] && vis[i-1][j]==0){
see++;
dfs(i-1,j);
vis[i-1][j]=0;
see--;
}
}
if(i>=0 && j-1>=0){
if(s[see]==a[i][j-1] && vis[i][j-1]==0){
see++;
dfs(i,j-1);
vis[i][j-1]=0;
see--;
}
}
if(i+1>=0 && j>=0){
if(s[see]==a[i+1][j] && vis[i+1][j]==0){
see++;
dfs(i+1,j);
vis[i+1][j]=0;
see--;
}
}
if(i>=0 && j+1>=0){
if(s[see]==a[i][j+1] && vis[i][j+1]==0){
see++;
dfs(i,j+1);
vis[i][j+1]=0;
see--;
}
}
}
int main(){
scanf("%d %d",&m,&n);
count=0;
for(int i=0;i<m;i++){
scanf("%c",&cc);
for(int j=0;j<n;j++){
scanf("%c",&a[i][j]);
vis[i][j]=0;
}
}
scanf("%c",&cc);
scanf("%s",s);
len=strlen(s);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][j]==s[0]){
see=1;
dfs(i,j);
}
}
}
printf("%d\n",count);
return 0;
}
Input :
4 5
snbsn
bakea
bkbbk
sebse
snakes
Output :
3
int EightDMove[8][2] = { { 0,1},{1,0},{1,1},{0,-1},{-1,0},{-1,-1},{1,-1},{-1,1} };
#define IS_VALID_MOVE(i,j) ( i>=0 && i<4 && j>=0 && j<5 )
int countOccZigZag(char maze[4][5], int i, int j, char *in)
{
/* Yes Match found and ends here */
if(*in == '\0')
return 1;
/* yet to match something */
int sum =0;
for (int k =0 ;k<8;k++)
{ int a = i+EightDMove[k][0];
int b =i+EightDMove[k][1];
if(IS_VALID_MOVE(a,b) && maze[a][b] == *in)
{
sum += countOccZigZag(maze,a,b,in+1);
}
}
return sum;
}
void test()
{
/* Initilaize the board and text */
char p[4][5] = {
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};
char target[] = {'S','N','A','K','E','\0'};
/* Call the util when there is a match */
int sum =0;
for (int i=0 ;i<4;i++)
for (int j=0;j<5;j++)
if (p[i][j] == *target )
sum += countOccZigZag(p,i,j,target+1);
printf ("Count : %d",sum);
}
A bruteforce recursion based solution in java without any optimization
public class SnakeFinder {
public static char board[][];
public static char[] tstr;
public static int maxr, maxc;
public static void main(String args[]) {
String str[] = { "SNBSN", "BAKEA", "BKBBK", "SEBSE" };
maxr = str.length;
maxc = str[0].length();
board = new char[maxr][maxc];
for (int s = 0; s < str.length; s++)
board[s] = str[s].toCharArray();
tstr = "SNAKES".toCharArray();
int count = 0;
for (int r = 0; r < maxr; r++) {
for (int c = 0; c < maxc; c++) {
if (board[r][c] == tstr[0]) {
count += find(r, c, 1);
}// if end
}// for c end
}// for r end
System.out.println(count);
}// end of main
//searches for the character targetString[i] from r, c
public static int find(int r, int c, int i) {
if (i == tstr.length)
return 1;
int count = 0;
if (r - 1 > -1 && board[r-1][c] == tstr[i])
count += find(r - 1, c, i + 1);
if (r + 1 < maxr && board[r+1][c] == tstr[i])
count += find(r + 1, c, i + 1);
if (c - 1 > -1 && board[r][c-1] == tstr[i])
count += find(r, c - 1, i + 1);
if (c + 1 < maxc && board[r][c+1] == tstr[i])
count += find(r, c + 1, i + 1);
return count;
}
}
/*
How many occurrences of a given search word can you find in a two-dimensional array
of characters given that the word can go up, down, left, right, and around 90 degree bends?
*/
int findSnake(char board[4][5], int x, int y, string word, int index,
vector<pair<int,int> > path) {
int back = (int)word.size() - 1;
char letter = word[index];
// base case: out of bounds
if(x < 0 || y < 0 || x > 3 || y > 4) {
return 0;
}
// base case: already visited
if(find(path.begin(), path.end(), pair<int,int>(x,y)) != path.end()) {
return 0;
}
path.push_back(pair<int,int>(x,y));
cout << "Visit (" << x << "," << y << ")" << endl;
// base case: snake chain broken
if(board[x][y] != letter) {
return 0;
}
// base case: snake chain succeeded
if(index == back) {
return 1;
}
int count = 0;
count += findSnake(board, x+1, y, word, index+1, path);
count += findSnake(board, x, y+1, word, index+1, path);
count += findSnake(board, x-1, y, word, index+1, path);
count += findSnake(board, x, y-1, word, index+1, path);
return count;
}
int countSnakes() {
char board[4][5] = {{'S','N','B','S','N'},
{'B','A','K','E','A'},
{'B','K','B','B','K'},
{'S','E','B','S','E'}};
int count = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 5; j++) {
vector<pair<int,int> > path;
if (board[i][j] == 'S') {
path.clear();
count += findSnake(board, i, j, "SNAKE", 0, path);
cout << "Found " << count << " snakes" << endl;
}
}
}
return count;
}
Recursion based solution in Java, that searches given word in all directions starting from every char in the input array. Tested with all possible combination, I hope it helps.
public static void main(String[] args) {
char inputArray[][] =
{{'S','N','B','S','N'},
{'B','A','K','E','A'},
{'B','K','B','B','K'},
{'S','E','B','S','E'}};
String wordToSearch = "SNAKE";
findWord(inputArray, wordToSearch);
}
private static void findWord(char[][] inputArray, String wordToSearch) {
//split given word to the char array
char[] givenWord = wordToSearch.toCharArray();
int countOfMatches = 0;
//find all possible word, with the same length as provided
for (int col = 0; col<inputArray.length; col++) {
for (int row = 0; row<inputArray[col].length; row++) {
//If the first chat matches the array element, start to search
int startChar = 0;
if (givenWord[startChar]==inputArray[col][row]) {
countOfMatches += findWord(inputArray, givenWord, col, row, startChar+1);
}
}
}
System.out.println(String.format("Found the word: %s %d times",
wordToSearch, countOfMatches));
}
private static int findWord(char[][] inputArray, char[] wordToSearch,
int col, int row, int startChar) {
//Check if the end of the word is reached
if(startChar<wordToSearch.length) {
int result = 0;
int[] newIndex = new int []{col,row+1};
//Try up to bottom
if (newIndex[1]<inputArray[col].length && wordToSearch[startChar]==inputArray[col][newIndex[1]]) {
result += findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
}
//Try bottom to up
newIndex[1] = row-1;
if (newIndex[1]>=0 && wordToSearch[startChar]==inputArray[col][newIndex[1]]) {
result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
}
//Reset the row
newIndex[1] = row;
//Try right to left
newIndex[0] = col-1;
if (newIndex[0]>=0 && wordToSearch[startChar]==inputArray[newIndex[0]][row]) {
result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
}
//Try left to right
newIndex[0] = col+1;
if (newIndex[0]<inputArray.length && wordToSearch[startChar]==inputArray[newIndex[0]][row]) {
result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
}
return result;
} else {
return 1;
}
}
public static int countWordsInMatrix(char[][] matrix, char[] inputString) {
int col = matrix[0].length;
int row = matrix.length;
int count = 0;
for (int i = 0; i < row - 1; i++) {
for (int j = 0; j < col - 1; j++) {
int find = search(matrix, row, col, i, j, inputString, 0);
count += find;
}
}
return count;
}
public static int search(char[][] matrix, int row, int col, int i, int j,
char[] inputString, int matchIndex) {
if (matchIndex == inputString.length)
return 1;
if (matrix[i][j] != inputString[matchIndex])
return 0;
else {
int count = 0;
if (i + 1 < row)
count += search(matrix, row, col, i + 1, j, inputString,
matchIndex + 1);
if (j + 1 < col)
count += search(matrix, row, col, i, j + 1, inputString,
matchIndex + 1);
if (i > 1)
count += search(matrix, row, col, i - 1, j, inputString,
matchIndex + 1);
if (j > 1)
count += search(matrix, row, col, i, j - 1, inputString,
matchIndex + 1);
return count;
}
}
Since nothing is mentioned in the question, I'm assuming that each character can repeat in array can be counted multiple times for a single occurrence of a string since characters can be repeated in the string itself.
My version of code in Java
public class Test{
static char[][] inpArray = {{'S','N','B','S','N'},
{'B','A','K','E','A'},
{'B','K','B','B','K'},
{'S','E','B','S','E'}};
public static void main(String args[]){
String inpString = "SNAKES";
int numOccurances = 0;
for(int i = 0; i < inpArray.length; i++)
{
for(int j = 0; j < inpArray[0].length; j++)
{
if(inpArray[i][j] == inpString.charAt(0))
numOccurances += findNewOccurance(inpString, i, j);
}
}
System.out.println("Number of occurances of "+inpString+" is "+numOccurances);
}
public static int findNewOccurance(String inpString, int row, int col)
{
int numOccurances = 0;
if(inpString.length() == 0)
return 0;
if(inpString.length() == 1 && inpString.charAt(0) == inpArray[row][col])
return 1;
if(inpString.charAt(0) != inpArray[row][col])
return 0;
else
{
String remainingString = inpString.substring(1, inpString.length());
System.out.println(remainingString);
if(row + 1 < inpArray.length)
numOccurances += findNewOccurance(remainingString, row+1, col);
if(row - 1 >= 0)
numOccurances += findNewOccurance(remainingString, row-1, col);
if(col + 1 < inpArray[0].length)
numOccurances += findNewOccurance(remainingString, row, col+1);
if(col - 1 >= 0)
numOccurances += findNewOccurance(remainingString, row, col-1);
}
return numOccurances;
}
}
My implementation below in C++ allows for reusing already visited characters. It allows users to specify a matrix size, then creates and randomly populates the matrix, then asks the user for a search string, and then runs DFS without any notion of explored nodes.
As FrederichCheng mentioned, the runtime would be O(M*N*8^(k-1)) for a large matrix of size (M, N) and a search string of length k. (Imagine for example what happens when the matrix is all A's and the search string is AA... (k times).)
#include <iostream>
#include <stack>
#include <set>
#include <string.h>
#include <stdlib.h>
#include <time.h>
typedef std::pair<int, int> Pair;
typedef std::set<Pair> NeighborSet;
int find_wordcount_from_index(char ** arr, int M, int N, int i, int j, char const * search, NeighborSet ** neighbors)
{
if (arr[i][j] == search[0])
{ // proceed
if (search[1] == 0)
{
std::cout << "Search successfully terminated at: (" << i << "," << j << ") " << std::endl;
return 1;
}
std::cout << "Exploring: (" << i << "," << j << ")" << std::endl;
int totalCount = 0;
NeighborSet n = neighbors[i][j];
typename NeighborSet::iterator it = n.begin();
std::cout << "Neighbors are: ";
for (; it != n.end(); ++it)
{
std::cout << "(" << it->first << "," << it->second << ") ";
}
std::cout << std::endl;
++search;
for (it = n.begin(); it != n.end(); ++it)
{
totalCount += find_wordcount_from_index(arr, M, N, it->first, it->second, search, neighbors);
}
--search;
return totalCount;
}
else
{
// std::cout << "Search failure at: (" << i << "," << j << ") " << std::endl;
return 0;
}
}
int find_wordcount_in_matrix(char ** arr, int M, int N, char const * search)
{
// memoize all neighbors
NeighborSet ** neighbors = new NeighborSet*[M];
for (int i = 0; i < M; ++i)
{
neighbors[i] = new NeighborSet[N];
for (int j = 0; j < N; ++j)
{
int neighborsRows[] = {i-1, i, i+1};
int neighborsCols[] = {j-1, j, j+1};
for (int k = 0; k < 3; ++k)
{
for (int l = 0; l < 3; ++l)
{
int row = neighborsRows[k], col = neighborsCols[l];
if (row >= 0 && row < M && col >= 0 && col < N)
{
if (row == i && col == j)
{
continue;
}
neighbors[i][j].insert(std::make_pair(row, col));
}
}
}
}
}
int totalCount = 0;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
totalCount += find_wordcount_from_index(arr, M, N, i, j, search, neighbors);
}
}
return totalCount;
}
int main(int argc, char ** argv)
{
int M = 4;
int N = 5;
if (argc > 1)
{
M = atoi(argv[1]);
}
if (argc > 2)
{
N = atoi(argv[2]);
}
srand(time(NULL));
char ** arr = new char*[M];
for (int i = 0; i < M; ++i)
{
arr[i] = new char[N];
for (int j = 0; j < N; ++j)
{
char r = 'A' + rand() % 26;
arr[i][j] = r;
std::cout << r << " ";
}
std::cout << std::endl;
}
while (true)
{
std::string search;
while (search.size() == 0)
{
std::cout << "Enter search string: ";
std::cin >> search;
}
std::cout << "Searching for: " << search << std::endl;
int totalCount = find_wordcount_in_matrix(arr, M, N, search.c_str());
std::cout << "Total count is: " << totalCount << std::endl << std::endl;
}
return 0;
}
#include <string.h>
#include <stdio.h>
const int N = 5,
M = 4;
int checkNeighbor(char arr[M][N], int i, int j, char str[], int next)
{
if(next == strlen(str)) return 1;
int counter = 0;
if(arr[i - 1][j] == str[next] && i - 1 >= 0)
counter += checkNeighbor(arr, i - 1, j, str, next + 1);
if(arr[i + 1][j] == str[next] && i + 1 < M)
counter += checkNeighbor(arr, i + 1, j, str, next + 1);
if(arr[i][j - 1] == str[next] && j - 1 >= 0)
counter += checkNeighbor(arr, i, j - 1, str, next + 1);
if(arr[i][j + 1] == str[next] && j + 1 < N)
counter += checkNeighbor(arr, i, j + 1, str, next + 1);
return counter;
}
int main()
{
char arr[M][N] = {'S', 'N', 'B', 'S', 'N',
'B', 'A', 'K', 'E', 'A',
'B', 'K', 'B', 'B', 'K',
'S', 'E', 'B', 'S', 'E'},
str[] = "SNAKES";
int counter = 0;
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
if(arr[i][j] == str[0])
counter += checkNeighbor(arr, i, j, str, 1);
printf("%d\n", counter);
return 0;
}
simple dfs whenever the letter 'S' is encountered.
//pat is the pattern to be searched.
//m is size of pattern,n1 & n2 dimensions of the 2-D array
void dfs(int x,int y,int index)
{
if(x<0 || y<0 || x>=n1 || y>=n2){return;}
if(vis[x][y]){return;}
vis[x][y]=1;
if(v[x][y]!=pat[index] && index==m-1){return;}
if(v[x][y]==pat[index] && index==m-1){ans++;}
dfs(x+1,y,index+1);
dfs(x-1,y,index+1);
dfs(x,y+1,index+1);
dfs(x,y-1,index+1);
return;
}
// java solution
public class WordCounter
{
private static class Result
{
int occurrences;
public Result(int n)
{
occurrences = n;
}
}
public static int count(char[][] matrix, String s)
{
int pos;
Result r = new Result(0);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
pos = 0;
count(matrix, s, i, j, pos, r);
}
}
return r.occurrences;
}
private static void count(char[][] matrix, String s, int i, int j, int pos, Result r)
{
if (pos >= s.length()) return;
char c = s.charAt(pos);
if (matrix[i][j] != c) return;
if ((matrix[i][j] == c) && (pos == matrix.length - 1)) {
r.occurrences++;
return;
}
if (i < matrix.length - 1) count(matrix, s, i + 1, j, pos + 1, r);
if (i > 0) count(matrix, s, i - 1, j, pos + 1, r);
if (j < matrix[0].length - 1) count(matrix, s, i, j + 1, pos + 1, r);
if (j > 0) count(matrix, s, i, j - 1, pos + 1, r);
}
public static void main(String[] args)
{
char[][] matrix = {
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};
String s = "SNAKE";
int n = count(matrix, s);
System.out.println("n = " + n);
}
}
1) Count word by using DFS from each cell
2) Java implementation of above approach
public static int countWord(char[][] a, String word)
{
int wordLength = word.length();
char[] current = new char[wordLength];
int row = a.length;
int col = a[0].length;
boolean[][] visited = new boolean[row][col];
int count = 0;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (!visited[i][j])
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}
}
}
return count;
}
private static int countWord(char[][] a, int i, int j, char[] current, int index, boolean[][] visited, String word,
int row, int col)
{
int count = 0;
if (isSafe(a, visited, i, j, row, col, index, word))
{
current[index] = a[i][j];
if (current[index] != word.charAt(index))
{
return 0;
}
if (index == word.length() - 1)
{
return 1;
}
visited[i][j] = true;
index++;
count += countWord(a, i + 1, j, current, index, visited, word, row, col);
count += countWord(a, i - 1, j, current, index, visited, word, row, col);
count += countWord(a, i, j + 1, current, index, visited, word, row, col);
count += countWord(a, i, j - 1, current, index, visited, word, row, col);
visited[i][j] = false;
}
return count;
}
private static boolean isSafe(char[][] a, boolean[][] visited, int i, int j, int row, int col, int index, String word)
{
if ((i >= 0 && i < row) && (j >= 0 && j < col) && (!visited[i][j]) && (index < word.length()))
{
return true;
}
return false;
}
Java:
To compute the time complexity, we can consider the searching path a DFS 4-way tree traversal with the depth equal to the length of searched string k - 1 (root's depth is 0), so searching each tree takes O(4^(k-1)) = O(2^2(k-1)) = O(2^2k). Since each node can be a root, there will be m*n (dimension of the map) trees to search. Therefore, the general time complexity is O(m*n*2^2k). Since 2^2k grows much faster than m*n, simply O(2^2k).
- FrederichCheng July 14, 2014If there is no turning back, it would be a 3-way tree search except that the root has 4 child nodes, but this would have little impact on the time complexity (O(4*3^(k-2)) = O(2^2k)).