# My 14ms Java solution.. space complexity- recursive stack+ O(mn)...time=O(n)

• public class Solution
{
public static boolean exist(char[][] board, String word)
{
if(word.length()>(board.length*board[0].length))
return false;

``````	boolean check=true;
int i=0;
ArrayList<Integer> temp = new ArrayList<Integer>();

boolean[][] truth= new boolean[board.length][board[0].length];

temp=search(word.charAt(i),board);
if(temp.isEmpty())
return false;

while (i<temp.size())
{
check = Match(temp.get(i),temp.get(i+1),word,0,board,truth);
if (check==true)
break;

i+=2;
}
return check;

}

static ArrayList<Integer> search(char a, char[][] board)
{
int i=0,j=0;
ArrayList<Integer> temp = new ArrayList<Integer>();
for(i=0;i<board.length;i++)
{
for(j=0;j<board[i].length;j++)
{
if(a==board[i][j])
{
}
}
}
return temp;
}

static boolean Match (int i,int j,String word,int count,char[][] board,boolean[][] truth)
{
boolean t1=false,t2=false,t3=false,t4=false;
if(count==((word.length())-1))
return true;
truth[i][j]=true;

if(i+1<board.length&&board[i+1][j]==word.charAt(count+1)&& truth[i+1][j]==false)
t1=Match(i+1,j,word,count+1,board,truth);

if(t1==true)
return t1;

if(j+1<board[i].length&&board[i][j+1]==word.charAt(count+1)&& truth[i][j+1]==false)

t2=Match(i,j+1,word,count+1,board,truth);

if(t2==true)
return t2;

if(j-1>=0&&board[i][j-1]==word.charAt(count+1)&&truth[i][j-1]==false)
t3=Match(i,j-1,word,count+1,board,truth);

if(t3==true)
return t3;

if(i-1>=0&&board[i-1][j]==word.charAt(count+1)&&truth[i-1][j]==false)
t4=Match(i-1,j,word,count+1,board,truth);

if(t4==true)
return t4;

else
{
truth[i][j]=false;
return false;
}
}
``````

}

• part of the code is places outside the preview section...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.