Java 6ms DFS solution, easy to understand and relatively short


  • 4
    D

    Idea is simple: the only 'O's that will NOT change to 'X's are those at the edges and those horizontally or vertically connected to the 'O's at the edges. So, first find out all the 'O's at the edges, mark them as 'M', and keep checking their surrounding 'O's and mark them as 'M'. Then loop the board again, change 'O's to 'X's and change those who was marked as 'M's to 'O's. Done.

    public class Solution {
        public void solve(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if ((i == 0 || i == board.length-1 || j == 0 || j == board[i].length-1) && (board[i][j] == 'O')) {
                        board[i][j] = 'M';
                        connected(i, j, board);
                    }
                }
            }
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    else if (board[i][j] == 'M') {
                        board[i][j] = 'O';
                    }       
                }
            }
        }
        
        public void connected(int i, int j, char[][] board) {
            if (i-1 > 0 && board[i-1][j] == 'O') {
                board[i-1][j] = 'M';
                connected(i-1, j, board);
            }
            if (i+1 < board.length-1 && board[i+1][j] == 'O') {
                board[i+1][j] = 'M';
                connected(i+1, j, board);
            }
            if (j-1 > 0 && board[i][j-1] == 'O') {
                board[i][j-1] = 'M';
                connected(i, j-1, board);
            }
            if (j+1 < board[i].length-1 && board[i][j+1] == 'O') {
                board[i][j+1] = 'M';
                connected(i, j+1, board);
            }
        }
    }

  • 0
    1

    why i+1 < board.length-1 j+1 < board[i].length-1 but not i+1 < board.length j+1 < board[i].length? why the second one get runtime error?


  • 0
    D

    It's just a minor difference, and you can keep it i+1 < board.length. Since the 'O's on the edges (board.lengh-1 & board[I].length-1) will be looped through in solve() function and marked with 'M' anyway, it will be just fine to stop at board.length-2 and board[I].length-2 while finding connected 'O's in the connected() function. Otherwise, some 'O's on the edges could be checked twice which I don't think it's a big deal, and it won't impact the performance much.

    About the runtime error, it shouldn't give you runtime error if you just change it to i+1 < board.length. I guess the problem is at somewhere else.


  • 0
    C

    Hi, I have got a question here. In your connected method, I add '=' to all the four if conditions, and it give a run time error. But If I just add '=' to three of them, then it is accepted....Can you explain this?


  • 0
    C

    I think adding'=' should not affect the running result.


  • 0
    D

    I saw that the stackoverflow error occurs when the recursion is called too many times that exceed the stack section. If you add '=' which means the recursion will check the edges, so it could throw runtime error on some extreme cases such as having a board[250][250] with 'O's for every element on the edges, which will make the recursion runs throughout all edges at once along with other 'O's connected to them. In such case, it might run out the stack and give runtime error.


  • 0
    D

    After digging into the runtime error, I have to correct that it does have a difference and it will show stackoverflow runtime error if you include the edges in recursion function due to some corner cases. The explanation is shown above.


  • 0
    C

    But I think the algorithm has changed every 'O' to 'M' on the edge, so when it comes to the edge, the second condition in the if won't satisfy. So it won't run the recursive calls on the edge. Am I right?


  • 0
    D

    Not really. If the board has all elements with 'O's on all four edges, when the solve() function runs for the first time checking board[0][0] and get an 'O', it marks 'M' and goes to connected() function which checks all surrounding 'O's and edges inclusive, so the connected(0, 0, board) WILL check board[0][1], board[0][2], board[0][3]... and board[1][0], board[2][0], board[3][0]... until all the edges are checked and marked 'M'. Then the solve() function will continue to check board[0][1], etc. However, before solve() function checks board[0][1], it might run out of stack by calling too many recursions.


  • 0
    C

    Yes, you are right. Thank you :)


  • 0
    O

    @davidsunsbk
    But even if without checking the four edges in solve(), it could still cause stack overflow on a zigzag case. (Just like the same reason why 200. Number of Islands cannot be solved by DFS.) Do you agree?


Log in to reply
 

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