Published in

Nerd For Tech

# Problem statement

`Input: board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"Output: true`
`Input: board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "SEE"Output: true`
`Input: board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCB"Output: false`
`- m == board.length- n = board[i].length- 1 <= m, n <= 6- 1 <= word.length <= 15- board and word consists of only lowercase and uppercase English letters.`

# Explanation

## DFS algorithm

`// function main- set x[4] = {1, -1, 0, 0}      y[4] = {0, 0, 1, -1}- initialize i and j- loop for i = 0; i < board.size(); i++  - loop for j = 0; j < board[0].size(); j++    - if dfs(board, i, j, 0, word)      - return true// function dfs(board, i, j, position, word)- if position >= word.size()  - return true// call resolvable function to check the boundary conditions of grid// and see if the char at word position matches the board index board[i][j]- if resolvable(board, i, j, position, word)  - char t = board[i][j]  - board[i][j] = '.'  // if the current char matches we move across all the four directions to match the next char  - loop for k = 0; k < 4; k++    - if dfs(board, i + x[k], j + y[k], position + 1, word)      - return true  - board[i][j] = t- return false// function resolvable(board, i, j, position, word)- return i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && board[i][j] == word[position]`

## C++ solution

`class Solution {int x[4] = {1, -1, 0, 0};int y[4] = {0, 0, 1, -1};public:bool resolvable(vector<vector<char>>& board, int i, int j, int position, string word){    return (i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && board[i][j] == word[position]);}public:bool dfs(vector<vector<char>>& board, int i, int j, int position, string word){    if(position >= word.size()){        return true;    }    if(resolvable(board, i, j, position, word)){        char t = board[i][j];        board[i][j] = '.';        for(int k = 0; k < 4; ++k){            if(dfs(board, i + x[k], j + y[k], position + 1, word)){                return true;            }        }        board[i][j] = t;    }    return false;}public:bool exist(vector<vector<char>>& board, string word) {    int i, j;    for(i = 0; i < board.size(); i++){        for(j = 0; j < board[0].size(); j++){            if(dfs(board, i, j, 0, word)){                return true;            }        }    }    return false;}};`

## Golang solution

`var x [4]intvar y [4]intfunc resolvable(board [][]byte, i, j, position int, word string) bool {    return i >= 0 && i < len(board) && j >= 0 && j < len(board[0]) && word[position] == board[i][j]}func dfs(board [][]byte, i, j, position int, word string) bool {    if position >= len(word) {        return true    }    if resolvable(board, i, j, position, word) {        t := board[i][j]        board[i][j] = '.'        for k := 0; k < 4; k++ {            if dfs(board, i + x[k], j + y[k], position + 1, word) {                return true            }        }        board[i][j] = t    }    return false}func exist(board [][]byte, word string) bool {    x = [...]int{1, -1, 0, 0}    y = [...]int{0, 0 , 1, -1}    for i := 0; i < len(board); i++ {        for j := 0; j < len(board[0]); j++ {            if dfs(board, i, j, 0, word) {                return true            }        }    }    return false}`

## Javascript solution

`var x = [1, -1, 0, 0];var y = [0, 0, 1, -1];function resolvable(board, i, j, position, word){    return i >= 0 && i < board.length && j >= 0 && j < board[0].length && word[position] == board[i][j]}function dfs(board, i, j, position, word){    if(position >= word.length) {        return true;    }    if(resolvable(board, i, j, position, word)) {        var t = board[i][j];        board[i][j] = '.';        for(var k = 0 ; k < 4; k++){            if(dfs(board, i + x[k], j + y[k], position + 1, word)){                return true;            }        }        board[i][j] = t;    }    return false;}var exist = function(board, word) {    for(var i = 0; i < board.length; i++){        for(var j = 0; j < board[0].length; j++){            if(dfs(board, i, j, 0, word)) {                return true;            }        }    }    return false;}`
`Input: board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]       word = "SEE"Step 1: initialize i, jStep 2: loop for i = 0; i < board.size()        0 < 3        true        loop for j = 0; j < board[0].size()        0 < 4        true        dfs(board, i, j, 0, word)        dfs(board, 0, 0, 0, word)Step 3: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && j >= 0 && 0 < 4 && word[0] == board[0][0]          - true && 'S' == 'A'          - false        return falseStep 4: We reach at step 2 and increment j        i = 0        j = 1        dfs(board, i, j, 0, word)        dfs(board, 0, 1, 0, word)Step 5: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 1 >= 0 && 1 < 4 && word[0] == board[0][1]          - true && 'S' == 'B'          - false        return falseStep 6: We reach at step 2 and increment j        i = 0        j = 2        dfs(board, i, j, 0, word)        dfs(board, 0, 2, 0, word)Step 7: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 2 >= 0 && 2 < 4 && word[0] == board[0][2]          - true && 'S' == 'C'          - false        return falseStep 8: We reach at step 2 and increment j        i = 0        j = 3        dfs(board, i, j, 0, word)        dfs(board, 0, 3, 0, word)Step 9: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 3 >= 0 && 3 < 4 && word[0] == board[0][3]          - true && 'S' == 'E'          - false        return falseStep 10: We reach at step 2 and increment j        i = 0        j = 4        dfs(board, i, j, 0, word)        dfs(board, 0, 3, 0, word)Step 11: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 3 >= 0 && 4 < 4 && word[0] == board[0][3]          - false && 'S' == 'E'          - false        return falseStep 12: We reach at step 2 and increment i and j is 0        i = 1        j = 0        dfs(board, i, j, 0, word)        dfs(board, 1, 0, 0, word)Step 13: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 0 >= 0 && 0 < 4 && word[0] == board[1][0]          - true && 'S' == 'S'          - true          - t = board[i][j]          - t = 'S'          - board[i][j] = '.'          - board[1][0] = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x[0], 0 + y[0], 0 + 1, word)            - dfs(board, 1 + 1, 0 + 0, 0 + 1, word)            - dfs(board, 2, 0 + 0, 1, word)        // recursive call to dfs function        if position >= word.size()           1 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 0 >= 0 && 0 < 4 && word[1] == board[2][0]          - true && 'E' == 'A'          - false          k++          k = 1          loop for k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x[1], 0 + y[1], 0 + 1, word)            - dfs(board, 1 - 1, 0 + 0, 0 + 1, word)            - dfs(board, 0, 0, 1, word)        // recursive call to dfs function        if position >= word.size()           1 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 0 >= 0 && 0 < 4 && word[1] == board[0][0]          - true && 'E' == 'A'          - false          k++          k = 2          loop for k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x[2], 0 + y[2], 0 + 1, word)            - dfs(board, 1 + 0, 0 + 1, 0 + 1, word)            - dfs(board, 1, 1, 1, word)        // recursive call to dfs function        if position >= word.size()           1 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 1 >= 0 && 1 < 4 && word[1] == board[1][1]          - true && 'E' == 'F'          - false          k++          k = 3          loop for k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x[3], 0 + y[3], 0 + 1, word)            - dfs(board, 1 + 0, 0 - 1, 0 + 1, word)            - dfs(board, 1, -1, 1, word)        // recursive call to dfs function        if position >= word.size()           1 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && -1 >= 0 && 1 < 4 && word[1] == board[1][1]          - false          k++          k = 4          loop for k < 4            - false        return falseStep 14: We reach at step 2 and increment i and j is 0        i = 1        j = 1        dfs(board, i, j, 0, word)        dfs(board, 1, 1, 0, word)        This is false since word[0] != board[1][1]        'S' != 'F'Step 15: We reach at step 2 and increment i and j is 1        i = 1        j = 2        dfs(board, i, j, 0, word)        dfs(board, 1, 2, 0, word)        This is false since word[0] != board[1][2]        'S' != 'C'Step 16: We reach at step 2 and increment i and j is 2        i = 1        j = 3        dfs(board, i, j, 0, word)        dfs(board, 1, 3, 0, word)Step 17: //in function dfs        if position >= word.size()           0 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word[0] == board[1][3]          - true && 'S' == 'S'          - true          - t = board[i][j]          - t = 'S'          - board[i][j] = '.'          - board[1][3] = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x[0], 3 + y[0], 0 + 1, word)            - dfs(board, 1 + 1, 3 + 0, 0 + 1, word)            - dfs(board, 2, 3, 1, word)        // recursive call to dfs function        if position >= word.size()           1 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 3 >= 0 && 3 < 4 && word[1] == board[2][3]          - true && 'E' == 'E'          - true          - t = board[i][j]          - t = 'E'          - board[i][j] = '.'          - board[2][3] = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x[0], 3 + y[0], 1 + 1, word)            - dfs(board, 2 + 1, 3 + 0, 2, word)            - dfs(board, 3, 3, 1, word)        // recursive call to dfs function        if position >= word.size()           2 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 3 >= 0 && 3 < 3 && 3 >= 0 && 3 < 4 && word[2] == board[2][3]          - false && 'E' == 'E'          - false          k++          k = 1          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x[1], 3 + y[1], 1 + 1, word)            - dfs(board, 2 - 1, 3 + 0, 2, word)            - dfs(board, 1, 3, 2, word)        // recursive call to dfs function        if position >= word.size()           2 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word[2] == board[1][3]          - false && 'E' == 'C'          - false          k++          k = 2          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x[2], 3 + y[2], 1 + 1, word)            - dfs(board, 2 + 0, 3 + 1, 2, word)            - dfs(board, 2, 4, 2, word)        // recursive call to dfs function        if position >= word.size()           2 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 4 >= 0 && 4 < 4 && word[2] == board[2][4]          - false          k++          k = 3          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x[3], 3 + y[3], 1 + 1, word)            - dfs(board, 2 + 0, 3 - 1, 2, word)            - dfs(board, 2, 2, 2, word)        // recursive call to dfs function        if position >= word.size()           2 >= 3           false        if resolvable(board, i, j, position, word)          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 2 >= 0 && 2 < 4 && word[2] == board[2][2]          - true && 'E' == 'E'          - true          - t = board[i][j]          - t = 'E'          - board[i][j] = '.'          - board[2][2] = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x[0], 2 + y[0], 2 + 1, word)            - dfs(board, 2 + 1, 2 + 0, 3, word)            - dfs(board, 2, 2, 3, word)        // recursive call to dfs function        if position >= word.size()           3 >= 3           trueStep 18: // Here we have covered all chars of the string "SEE" and found in the grid.         // So we return true from this recursive calls and return to exist function.So the answer we return is true.`

--

--

## More from Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.