• 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

Convert number to words java

Sort Stack in place

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Find and print longest consecutive number sequence in a given sequence in O(n)

Find if a binary tree is height balanced ?

DFS (Depth First Search)

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Common Ancestor in a Binary Tree or Binary Search Tree

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

Binary Tree in Java

Regular Expression Matching

Daughter’s Age VeryGood Puzzle

Leetcode: Merge Intervals

Find Percentage of Words matching in Two Strings

Possible sizes of bus to carry n groups of friends

Stickler thief

Calculate price of parking from parking start end time prices

Maximum sum contiguous subarray of an Array

Reversal of LinkedList

Level order traversal in Spiral form

Python Array String

Longest Increasing Subsequence

Client Server C program

SAP Interview Questions

FizzBuzz Solution C C++

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Facebook Interview Question : Interleave List

Implement LRU Cache

Trapping Rain Water

Find two non repeating elements in an array of repeating elements

Copyright © 2023 · Genesis Framework · WordPress · Log in