• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

LeetCode : Word Search

October 16, 2019 by Dhaval Dave

Word Search : Given a 2D board and a word, search if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where “adjacent” cells are those horizontally or vertically neighboring.
The same letter cell may not be used more than once.

Example:
board =
[
[‘Q’, ‘U’, ‘I’, ‘J’],
[‘O’, ‘F’, ‘C’, ‘E’],
[‘X’, ‘U’, ‘K’, ‘M’] ]

Given word = “QUICK”, return true.
Given word = “ICE”, return true.
Given word = “QUFM”, return false.
Backtracking Algorithm :
First traverse the given board and find x,y location such that grid[x][y] == word[0].
So that we can make a recursive call from the present coordinate in our pair of vectors.

Create a visited array of the same size of given board,
which will help us to keep track of visited coordinate so that we won’t make a recursive call again on the already used coordinate.

If a present coordinate leads us to the solution then
increment the length variable and check for another possible move in all four directions.

If any one of the four directions leads us to the solution ,
again make a recursive call from that coordinate.

If none of the 4 coordinate lead us to the solution,
backtrack by marking current coordinate vis[x][y] = false and also decrement length variable.

So that it can be used again, if a recursive call from another coordinate comes.

Repeat for whole matrix.

class Solution {
    public boolean exist(char[][] board, String word) {
	
	// first we need to find the starting position so we try all the index(row,column) as the potential starting point
        for (int i =0;i<board.length;i++)
        {
            for (int j =0;j<board[i].length;j++)
            {
	   // if yes then no need to do further calculation 
                if (checkExist(board,word,i,j,0))
                    return true;
            }
        }
        return false; // if all the positions are checked and no potential candidate(word not found) the return false;
    }
    
    public boolean isPossible(char [][] board,String word,int i,int j,int x){
      if (i>=board.length||i<0||j<0||j>=board[0].length 
           ||  x>=word.length() || word.charAt(x)!=board[i][j]
           || board[i][j]=='0')
              return false;
      // You can also segregate boundary, visibility condition etc.
return true;
    }	
    public boolean checkExist(char [][] board,String word,int i,int j,int x)
    {
          if(!isPossible (board,word,i,j,x) ) return false;   
	   
	// if we found the last character then return true;
        if (x==word.length()-1&&word.charAt(x)==board[i][j])
            return true;
        
	/* store the current character in a temporary variable 
	 this is done so that we can maintain which position is visited or not
	 here this character will be set to '0' and later after processing
         from this index it will be again restored it also faciliates 
         less memory as we are not creating any other 2-d array 
         to mark those indexes which are visited. */
        
        char temp = board[i][j];
        board[i][j]='0';

        x++; // increment the count of length or index of word by one.
        int iA = { 0, -1, 1, 0 };
        int jA = { 1, 0, 0, -1 };
        boolean b = false;
        for(int ia = 0; ia < iA.length; ia++ ){
            for(int ja = 0; ja < jA.length ; ja++) {
               b = b || checkExist(board, word, i+iA[ia], j+jA[ja],x)
            }
        }
  
        
	// restore the original value and return .
        board[i][j]=temp;
        return b;
    }
}

Find more LeetCode Questions

Time Complexity Analysis :-
From a particular position we can go into 4 other positions.

Let F(n) denotes the processing done by the function checkExist();
essentially this function is calling itself 4 times (for 4 directions)
question is how many times it will call itself

that will be K(length of word) as then word will already been found.

	T(n) = F(n)
	     = 4*F(n-1)...
		 = 4*4*F(n-2)...
		 = 4*4*4*4... (K times as K is the length of the word)
	

Total time complexity = M*N*(Pow(4,k));

Similar Articles

Filed Under: Amazon Interview Question, Google, LeetCode Tagged With: 2d matrix, Array, DFS, Matrix, Recursion

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Find the kth number with prime factors 3, 5 and 7

K’th Largest Element in BST when modification to BST is not allowed

Convert number to words java

Subset Sum Problem Dynamic programming

Handle duplicates in Binary Search Tree

Best Java Book | Top Java Programming Book for Beginners

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Sort Stack in place

Amazon Interview Experience – SDE Chennai

Get Minimum element in O(1) from input numbers or Stack

Find if a binary tree is height balanced ?

Find min element in Sorted Rotated Array (With Duplicates)

Generate next palindrome number

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Generic Object Oriented Stack with Template

Stickler thief

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

CodeChef Code SGARDEN

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

FizzBuzz Solution C C++

C Program for TAIL command of UNIX

Right view of Binary tree

Daughter’s Age VeryGood Puzzle

Mirror of Tree

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Print Power Set of a Set

Find the smallest window in a string containing all characters of another string

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Get K Max and Delete K Max in stream of incoming integers

Given a string, find the first character which is non-repetitive

Copyright © 2025 · Genesis Framework · WordPress · Log in