Using Stack to store the visited character, instead of 2D array


  • 1
        public bool ExistII(char[,] board, string word)
        {
            if (word == null || board == null || (board.GetLength(0) == 0 && board.GetLength(1) == 0) || word.Length == 0) return false;
    
            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    if (word[0] == board[i, j])
                        if (DFSWordSearch(board, i, j, 0, word))
                            return true;
                }
            }
    
            return false;
        }
        char tempchar = '#';
        Stack<char> tempCharStack = new Stack<char>();
        private bool DFSWordSearch(char[,] board, int i, int j, int index, string word)
        {
            if (index == word.Length)
                return true;
    
            if (i < 0 || j < 0 || i == board.GetLength(0) || j == board.GetLength(1) || word[index] != board[i, j])
                return false;
    
            tempCharStack.Push(board[i, j]);
            board[i, j] = '\n';
    
            bool check = DFSWordSearch(board, i, j + 1, index + 1, word) ||
                        DFSWordSearch(board, i + 1, j, index + 1, word) ||
                        DFSWordSearch(board, i, j - 1, index + 1, word) ||
                        DFSWordSearch(board, i - 1, j, index + 1, word);
    
            board[i, j] = tempCharStack.Pop();
    
            if (check == true)
                return true;
    
            return check;
        }
    

  • 0
    N

    Why use extra space, when the same array can be modified to mark as visited.

        int x[] = {0,0,1,-1};
        int y[] = {-1,1,0,0};
    
        public boolean wordSearch(char[][] board,String word){
            if(board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0){
                return false;
            }
            int m = board.length;
            int n = board[0].length;
            for(int i = 0 ;i<m;i++){
                for(int j = 0;j<n;j++){
                    //Do dfs only if the first letter of the word is found.
                    if(word.charAt(0) == board[i][j] && dfs(board,i,j,0,word)){
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean dfs(char[][] board, int i, int j, int currentWordIndex, String word){
            if(currentWordIndex == word.length()){
                return true;
            }
            if(i<0 || i>=board.length|| j<0 || j>=board[0].length || board[i][j]=='#'){
                return false;
            }
            boolean result = false;
            if(board[i][j] == word.charAt(currentWordIndex)){
                char temp = board[i][j];
                board[i][j] = '#';
                //mark it visited...
                for(int k = 0;k<4;k++){
                    int dx = x[k]+i;
                    int dy = y[k]+j;
                    result |= dfs(board,dx,dy,currentWordIndex+1,word);
                    if(result){
                        //This is just to save further iterations.
                        //before returning , its better to restore the older state.
                        board[i][j] = temp;
                        return true;
                    }
                }
                //restore the board back to original board by temp;
                board[i][j] = temp;
            }
            return result;
        }
    

Log in to reply
 

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