JP Morgan Interview Question
AssociatesCountry: United States
Verified solution :
class Solution {
private static int[][] adj = {{0,1},{0,-1},{1,0},{-1,0}};
public boolean exist(char[][] board, String word) {
boolean result=false;
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
Set<String> path = new HashSet<>();
if(existRecursive(board,word,0,i,j,path)){
return true;
}
}
}
return result;
}
public boolean existRecursive(char[][] board, String word,int pos,int x, int y,Set<String> path) {
if(pos>=word.length()){
return true;
}
if(x>=0 && x<board.length
&& y>=0 && y<board[x].length
&& !path.contains(x+","+y) && word.charAt(pos)==board[x][y]){
path.add(x+","+y);
for(int j=0;j<adj.length;j++){
int x1=x+adj[j][0];
int y1=y+adj[j][1];
if(existRecursive(board,word,pos+1,x1,y1,path)){
return true;
}
}
path.remove(x+","+y);
}
return false;
}
}
package main
import "fmt"
type input struct{
grid [][]uint8
word string
w int
x int
y int
}
type gridOps interface{
isWordPresentInGrid() bool
SearchInGrid()
IsRight() bool
IsLeft() bool
IsUp() bool
IsDown()
}
func (ip *input) IsRight() bool{
if ip.y == len(ip.word)-1{
return false
}
if ip.word[ip.w] == ip.grid[ip.x][ip.y+1]{
return true
}
return false
}
func (ip *input) IsLeft() bool{
if ip.y == 0{
return false
}
if ip.word[ip.w] == ip.grid[ip.x][ip.y-1]{
return true
}
return false
}
func (ip *input) IsUp() bool{
if ip.x == 0{
return false
}
if ip.word[ip.w] == ip.grid[ip.x-1][ip.y]{
return true
}
return false
}
func (ip *input) IsDown() bool{
if ip.x == len(ip.word)-1{
return false
}
if ip.word[ip.w] == ip.grid[ip.x+1][ip.y]{
return true
}
return false
}
func (ip *input) SearchInGrid() bool{
ip.w = ip.w + 1
if ip.w < len(ip.word) {
if ip.IsRight() {
ip.SearchInGrid()
}else if ip.IsLeft() {
ip.SearchInGrid()
}else if ip.IsUp() {
ip.SearchInGrid()
}else if ip.IsDown() {
ip.SearchInGrid()
} else{
//fmt.Println("word not found")
return false
}
}else{
return true
}
return false
}
func (ip *input)isWordPresentInGrid() bool{
outer:
for w := 0; w < len(ip.word); w++{
for i := range ip.grid{
for j := range ip.grid{
if ip.grid[i][j] != ip.word[w]{
continue
} else{
if ip.SearchInGrid(){
break outer
}
}
}
}
}
return false
}
func main() {
g := [][]uint8{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}
ip := input{grid: g, word : "ABCB"}
if ip.isWordPresentInGrid(){
fmt.Println("word found")
}else{
fmt.Println("word not found")
}
}
This is one of the quick solution. Assuming only characters appear in the board be A-Z
- dadakhalandhar March 09, 2018