# 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 = {1, -1, 0, 0}      y = {0, 0, 1, -1}- initialize i and j- loop for i = 0; i < board.size(); i++  - loop for j = 0; j < board.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.size() && board[i][j] == word[position]`

## C++ solution

`class Solution {int x = {1, -1, 0, 0};int y = {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.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.size(); j++){            if(dfs(board, i, j, 0, word)){                return true;            }        }    }    return false;}};`

## Golang solution

`var x intvar y intfunc resolvable(board [][]byte, i, j, position int, word string) bool {    return i >= 0 && i < len(board) && j >= 0 && j < len(board) && 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); 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.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.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.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.size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && j >= 0 && 0 < 4 && word == board          - 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.size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 1 >= 0 && 1 < 4 && word == board          - 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.size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 2 >= 0 && 2 < 4 && word == board          - 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.size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 3 >= 0 && 3 < 4 && word == board          - 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.size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 3 >= 0 && 4 < 4 && word == board          - 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.size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 0 >= 0 && 0 < 4 && word == board          - true && 'S' == 'S'          - true          - t = board[i][j]          - t = 'S'          - board[i][j] = '.'          - board = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x, 0 + y, 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.size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 0 >= 0 && 0 < 4 && word == board          - 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, 0 + y, 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.size && word[position] == board[i][j]          - 0 >= 0 && 0 < 3 && 0 >= 0 && 0 < 4 && word == board          - 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, 0 + y, 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.size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 1 >= 0 && 1 < 4 && word == board          - 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, 0 + y, 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.size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && -1 >= 0 && 1 < 4 && word == board          - 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 != board        '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 != board        '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.size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word == board          - true && 'S' == 'S'          - true          - t = board[i][j]          - t = 'S'          - board[i][j] = '.'          - board = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 1 + x, 3 + y, 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.size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 3 >= 0 && 3 < 4 && word == board          - true && 'E' == 'E'          - true          - t = board[i][j]          - t = 'E'          - board[i][j] = '.'          - board = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x, 3 + y, 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.size && word[position] == board[i][j]          - 3 >= 0 && 3 < 3 && 3 >= 0 && 3 < 4 && word == board          - 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, 3 + y, 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.size && word[position] == board[i][j]          - 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word == board          - 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, 3 + y, 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.size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 4 >= 0 && 4 < 4 && word == board          - 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 + y, 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.size && word[position] == board[i][j]          - 2 >= 0 && 2 < 3 && 2 >= 0 && 2 < 4 && word == board          - true && 'E' == 'E'          - true          - t = board[i][j]          - t = 'E'          - board[i][j] = '.'          - board = '.'          loop for k = 0; k < 4            - dfs(board, i + x[k], j + y[k], position + 1, word)            - dfs(board, 2 + x, 2 + y, 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.`

--

--