C# DFS. Simple and well formatted


  • 0
    D
    public class Solution {
        
        public bool Exist(char[,] board, string word) {
            int m = board.GetLength(0);
            int n = board.GetLength(1);
            bool[,] mesh = new bool[m,n];
            for (int i = 0; i < m; i++){
                for (int j = 0; j < n; j++){
                    mesh[i, j] = false;
                }
            }
            for (int i = 0; i < m; i++){
                for (int j = 0; j < n; j++){
                    var result = dfs(board, i, j, word, 0, mesh, m, n);
                    if (result){
                        return true;
                    }
                }
            }
            return false;
        }
        public bool dfs(char[,] board, int i, int j, string word, int index, bool[,] mesh, int m, int n){
            if (index == word.Length){
                return true;
            }
            if (i < 0 || j < 0 || i > m - 1 || j > n - 1){
                return false;
            }
            if (board[i, j] != word[index]){
                return false;
            }
            if (mesh [i, j]){
                return false;
            }
            mesh[i, j] = true;
            var result = dfs(board, i - 1, j, word, index + 1, mesh, m, n) || dfs(board, i, j - 1, word, index + 1, mesh, m, n) || 
                         dfs(board, i + 1, j, word, index + 1, mesh, m, n) || dfs(board, i, j + 1, word, index + 1, mesh, m, n);
            mesh[i, j] = false;
            return result;
        }
    }

  • 0
    T

    hi, i had a question that
    why shoud give a false to mesh[i][j] after take 4 direction dfs()?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.