Correct C# solution in O(m*n) time and O(1) memory usage


  • 0
    E
    public int CountBattleships(char[,] board) {
        var count = 0;
        for(var i = 0; i <board.GetLength(0); i++) {
            for(var j = 0; j < board.GetLength(1); j++) {
                if(board[i,j] == 'X' && (!HasNeighbor(i, j, board) || IsXPieceTopLeftHorizontal(i , j, board) || IsXPieceTopVertical(i, j, board))) {
                    count++;
                } 
            }
        }
        return count;
    }
    
    private bool HasNeighbor(int i, int j, char[,] board) {
        if(i > 0 && board[i-1, j] == 'X') return true;
        if(j > 0 && board[i, j - 1] == 'X') return true;
        if(i < board.GetLength(0) - 1 && board[i + 1, j] == 'X') return true;
        if(j < board.GetLength(1) - 1 && board[i, j + 1] == 'X') return true;
        return false;
    }
    
    private bool IsXPieceTopLeftHorizontal(int i, int j, char[,] board) {
        // Is board piece horizontal ship
        if((j > 0 && board[i, j - 1] == 'X') || (j < board.GetLength(1) - 1 && board[i, j + 1] == 'X')) {
            return j == 0 || board[i, j - 1] != 'X';
        }
        
        return false;
    }
    
    private bool IsXPieceTopVertical(int i, int j, char[,] board) {
        // Is board piece vertical ship
        if((i < board.GetLength(0) - 1 && board[i + 1, j] == 'X') || (i > 0 && board[i-1, j] == 'X')) {
            return i == 0 || board[i - 1, j] != 'X';
        }
        
        return false;

Log in to reply
 

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