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


  • 0
    K

    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])
    			{
    				temp.add(i);
    				temp.add(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;
    	}
    }
    

    }


  • 0
    K

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


Log in to reply
 

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