DFS solution in Swift


  • 0
    V
    class Solution {
        
        struct LandNode {
            var row : Int
            var col : Int
        }
        
        func numIslands(_ grid: [[Character]]) -> Int {
            let row_vector = [0,0,-1,1]
            let col_vector = [-1,1,0,0]
            
            guard let first = grid.first, first.count > 0 else { return 0 }
            
            let width = grid[0].count
            let height = grid.count
            
            let max_row = height - 1
            let max_col = width - 1
            
            var count = 0
            var stack : [LandNode] = []
            var visited : [Int : Int] = [:]
            
            for i in 0..<height{
                
                for j in 0..<width{
                    let pos = i*width + j
                    
                    if isLand(char: grid[i][j]) && visited[pos] == nil{
                        
                        count += 1
                        stack.insert(LandNode(row: i, col: j), at: 0)
                        
                        // DFS
                        while !stack.isEmpty{
                            let top = stack.removeFirst()
                            visited[top.row * width + top.col ] = 1
                            
                            for v in 0...3 {
                                let n_row = top.row + row_vector[v]
                                let n_col = top.col + col_vector[v]
                                
                                if (n_row >= 0 && n_row <= max_row && n_col >= 0 && n_col <= max_col){
                                    
                                    if isLand(char: grid[n_row][n_col]) && visited[n_row * width + n_col] == nil{
                                        stack.insert(LandNode(row: n_row, col: n_col), at: 0)
                                    }
                                }
                            }
                            
                        }
                    }
                }
            }
            return count
        }
        
        func isLand(char: Character) -> Bool {
            return char == Character("1")
        }
    }
    

Log in to reply
 

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