OJ seems to accept a brute force solution such as this one.


  • 1
    B

    Don't we want OJ to reject brute force solutions? OJ currently seems to accept even the following...

    //keep going through the board and flip an O into a $ if it's either at the boarder or next to a $
    //stop when you can't flip any more O
    //then go through the board one last time to flip a $ into an O and everything else into a X
        public class Solution {
            public void solve(char[][] board) {
                int height = board==null?0:board.length;
                int width = height==0?0:board[0].length;
                boolean changed = false;
                do {
        	        changed = false;
        		    for(int i=0;i<height;i++){
        		        for(int j=0;j<width;j++){
        		            if(board[i][j] == 'O' && (isBorder(board, i, j) || isNextToDollar(board, i, j)) ) {
        		        	    board[i][j] = '$';
        		        	    changed = true;
        		            }
        		        }
        		    }
                }while(changed);
                
                for(int i=0;i<height;i++){
                    for(int j=0;j<width;j++){
                    	board[i][j] = board[i][j]=='$'? 'O':'X';
                    }
                }
            }
            private boolean isBorder(char[][] board, int i, int j) {
                int height = board==null?0:board.length;
                int width = height==0?0:board[0].length;
                if(i==0 || j==0 || i==height-1 || j==width-1) return true;
                return false;
            }
            private boolean isNextToDollar(char[][] board, int i, int j) {
                int height = board==null?0:board.length;
                int width = height==0?0:board[0].length;
                int x, y;
                x = i-1; y=j;
                if(x>=0 && x<=height-1 && y>=0 && y<=width-1 && board[x][y]=='$') return true;
                x = i+1; y=j;
                if(x>=0 && x<=height-1 && y>=0 && y<=width-1 && board[x][y]=='$') return true;
                x = i; y = j-1;
                if(x>=0 && x<=height-1 && y>=0 && y<=width-1 && board[x][y]=='$') return true;
                x = i; y = j+1;
                if(x>=0 && x<=height-1 && y>=0 && y<=width-1 && board[x][y]=='$') return true;
                return false;
            }
        }

  • 0
    S

    I do not think your solution is brute force. What is elegant solution of this problem in your mind?


  • 0
    B

    hm... what's a brute force solution in your mind then? :)

    In my opinion, an elegant solution should be O(n) instead of O(n^2). You can achieve that by doing a bfs search from an edge O...

    For this solution, I think the worse case is all O inside the X border with just one opening at the bottom right corner.


  • 2

    Looks like your solution needs O(n^4) in worst case,
    Each traverse in do-while loop needs O(n^2) time.
    For image below, in each traverse you only be able to update one node while the update is from right to left or from bottom to top.

    XXXXXXXXXXXXXXXXXXXXXXXX

    XOOOOOOOOOOOOOOOOX

    XOXXXXXXXXXXXXXXXXXXXOX

    XOOOOOOOOOOOOOOXOX

    XXXXXXXXXXXXXXXXXXXXXOX

    OJ only helps to improve, no reason to blame OJ for not doing in a perfect way.


Log in to reply
 

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