Java Solution - Without extra space.


  • 0
    M

    The basic logic of this algorithm is - If you have 'X' in [i-1][j] or [i][j-1] position then the ship is already explored and the current position is part of the previous ship or empty. So, don't increase the count.

    class Solution {
        public int countBattleships(char[][] board) {
            int count = 0;
            for(int i = 0; i< board.length; i++) {
                for(int j=0; j<board[i].length; j++) {
                    if(i > 0 && board[i-1][j] == 'X') { //already explored ship.
                        continue;
                    }
                    if(j > 0 && board[i][j-1] == 'X') { //already explored ship.
                        continue;
                    }
                    if(board[i][j] == 'X') { //new ship.
                        count++;
                    }
                    
                }
            }
            return count;
        }
    }
    
    

Log in to reply
 

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