[C++, Java, Kotlin] Simple Explained Solution ✅
Approach\nSo, the idea is to go through all the positions, and if a position in the matrix contains the first character of the word, I start a depth-first searc
# Approach\nSo, the idea is to go through all the positions, and if a position in the matrix contains the first character of the word, I start a depth-first search starting from that position.\nAt each step, I check if I can go left, right, up, or down (if those positions\u2019 characters match the next character in the word) and continue. If I get to the end of the word, then it exists.\n\n# Complexity\n- Time complexity:\n$$O((mn)^2)$$\n\n- Space complexity:\n$$O(2mn)$$\n\n# Code\n```kotlin []\nclass Solution {\n    var dirs = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)\n    var board = arrayOf<CharArray>()\n    var word = ""\n    fun exist(board: Array<CharArray>, word: String): Boolean {\n        this.board = board\n        this.word = word\n        \n        var visited = Array(board.size) { BooleanArray(board[0].size) }\n        for (i in board.indices)\n            for (j in board[0].indices)\n                if (board[i][j] == word[0] && check(i, j, 0, visited))\n                    return true\n        return false\n    }\n    fun check(i: Int, j: Int, strIdx: Int, visited: Array<BooleanArray>): Boolean {\n        if (strIdx == word.length - 1) return true\n        visited[i][j] = true\n        var next = word[strIdx + 1]\n        for ((x, y) in dirs) {\n            if (i + x !in board.indices || j + y !in board[0].indices) continue\n            if (board[i + x][j + y] != next || visited[i + x][j + y]) continue\n            \n            if (check(i + x, j + y, strIdx + 1, visited)) return true\n        }\n        visited[i][j] = false\n        return false\n    }\n}\n```\n```Java []\npublic class Solution {\n    private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n    private char[][] board;\n    private String word;\n\n    public boolean exist(char[][] board, String word) {\n        this.board = board;\n        this.word = word;\n\n        boolean[][] visited = new boolean[board.length][board[0].length];\n        for (int i = 0; i < board.length; i++) {\n            for (int j = 0; j < board[0].length; j++) {\n                if (board[i][j] == word.charAt(0) && check(i, j, 0, visited)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n\n    private boolean check(int i, int j, int strIdx, boolean[][] visited) {\n        if (strIdx == word.length() - 1) {\n            return true;\n        }\n        visited[i][j] = true;\n        char next = word.charAt(strIdx + 1);\n        for (int[] dir : dirs) {\n            int x = i + dir[0];\n            int y = j + dir[1];\n            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length\n                    && board[x][y] == next && !visited[x][y]) {\n                if (check(x, y, strIdx + 1, visited)) {\n                    return true;\n                }\n            }\n        }\n        visited[i][j] = false;\n        return false;\n    }\n}\n\n```\n```C++ []\nclass Solution {\nprivate:\n    vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n    vector<vector<char>> board;\n    string word;\n\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        this->board = board;\n        this->word = word;\n\n        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));\n        for (int i = 0; i < board.size(); i++) {\n            for (int j = 0; j < board[0].size(); j++) {\n                if (board[i][j] == word[0] && check(i, j, 0, visited)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n\nprivate:\n    bool check(int i, int j, int strIdx, vector<vector<bool>>& visited) {\n        if (strIdx == word.length() - 1) {\n            return true;\n        }\n        visited[i][j] = true;\n        char next = word[strIdx + 1];\n        for (const auto& dir : dirs) {\n            int x = i + dir.first;\n            int y = j + dir.second;\n            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size()\n                    && board[x][y] == next && !visited[x][y]) {\n                if (check(x, y, strIdx + 1, visited)) {\n                    return true;\n                }\n            }\n        }\n        visited[i][j] = false;\n        return false;\n    }\n};\n```\n
['Kotlin']