Interesting use of DFS

79. Word Search(Leetcode)

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of a 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 =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

First, you might think of tackling it down the usual way of reverse engineering(get output and try to backtrack to source and develop an algorithm along the way) and maybe it might work. The most amazing thing about this question is the answer is actually given to you in the question.

First Examine all the keywords given to you in the question, usually, the answer lies inside. Words like search are trigger words, at least for me. So knowing you will have to create something like a search algorithm, first examine all the search algorithms you know. Don’t worry if you don’t get it the first time. Keep thinking thought. Hint: I can already see a repetition of processes in solving the question ie: you find the first element and then find the next adjacent and so on.

Obviously, if you are stuck ask interviewer clarifying questions and stay calm(What I tell myself when I am in an interview).

Let’s pick up from where we left off. There is repetition in searching characters of the word given so I can think about recursion. Wait, recursion what’s some search algorithm that is implemented using recursion. Well many but which one actually traverses all the nodes/elements of the array. This narrows down the answer to only BFS and DFS. Well, it really can’t be BFS as we are trying to traverse deeper and we are less concerned with finding all adjacent element(just one), so we are actually going deeper(finding the next adjacent element that is the next character in the word). Well now that we know it’s DFS, we can just start implementing it. Am just going to lay down the whole solution with comments and hope you got it from here.

Time complexity: The first 2 nested loops give us Big O(N*M) where M is #of rows and n is the #of columns(worst case where no char is found in the grid). Analyzing

//Extended part of the problem 

import java.io.*;
import java.util.*;

class Solution {
// Determine if we can find the input word in the grid by taking a
// path through adjacent letters.
public static boolean findWord(char[][] grid, String word) {

if (grid.length == 0 && grid[0].length == 0) return false; // base case

for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(word.charAt(0) == grid[i][j]){
//finding first char of word
if(dfs(grid,word,i , j, 0))
return true;
}
}
}
return false;
}

public static boolean dfs(char [][] grid, String tempStr,int i, int j,int k){
int m = grid.length;
int n= grid[0].length;

if(i <0 || j< 0 || i >= m || j >= n){
//checking out of bounds
return false;
}

// String out of bounds
if(k >= tempStr.length()){
return false;
}

//if char index not match with grid[i][j]
if(grid[i][j] != tempStr.charAt(k)){
return false;
}

//we know that we have come to the end of our rec call and found string.
if(k == tempStr.length()-1){
return true;
}
else if(dfs(grid,tempStr,i-1,j,k+1) //going left
|| dfs(grid,tempStr,i+1,j,k+1) //going right
|| dfs(grid,tempStr,i,j-1,k+1) //going up
|| dfs(grid,tempStr,i,j+1,k+1)){ //going down
return true;
}
return false;
}

public static void main(String[] args) {

char[][] testGrid = {{'c', 'b', 'd', 'k'},
{'e', 'a', 'q', 'c'},
{'d', 't', 't', 'a'},
{'z', 'w', 'b', 'i'}};

String[] testStrings = {"cat", "bike", "bat","cax", "ci", "cxxxxxxxa"};
for (String s : testStrings) {
findWord(testGrid, s);

System.out.println(findWord(testGrid, s));
}
}
}