Swift solution - Union Find, DFS


  • 0
    class Solution {
        func numIslands_UnionFind(_ grid: [[Character]]) -> Int {
            if grid.count == 0 || grid[0].count == 0 {
                return 0
            }
            
            let m = grid.count
            let n = grid[0].count
            let uf = UnionFind2(m, n, grid)
            
            for i in 0..<m {
                for j in 0..<n {
                    if grid[i][j] == "0" {
                        continue
                    }
                    let p = i * n + j
                    var q = 0
                    if i > 0 && grid[i - 1][j] == "1" {
                        q = p - n
                        uf.union(p, q)
                    }
                    if i < m - 1 && grid[i + 1][j] == "1" {
                        q = p + n
                        uf.union(p, q)
                    }
                    if j > 0 && grid[i][j - 1] == "1" {
                        q = p - 1
                        uf.union(p, q)
                    }
                    if j < n - 1 && grid[i][j + 1] == "1" {
                        q = p + 1
                        uf.union(p, q)
                    }
                }
            }
            
            return uf.getCount()
        }
        
        func numIslands_DFS(_ grid: [[Character]]) -> Int {
            if grid.count == 0 {
                return 0
            }
            
            let n = grid.count
            let m = grid[0].count
            var count = 0
            var grid = grid
            
            for i in 0..<n {
                for j in 0..<m {
                    if grid[i][j] == "1" {
                        DFS(&grid, i, j)
                        count += 1
                    }
                }
            }
            
            return count
        }
        
        func DFS(_ grid: inout [[Character]], _ i: Int, _ j: Int) {
            let n = grid.count
            let m = grid[0].count
            
            if i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != "1" {
                return
            }
            
            grid[i][j] = "0"
            DFS(&grid, i + 1, j)
            DFS(&grid, i - 1, j)
            DFS(&grid, i, j + 1)
            DFS(&grid, i, j - 1)
        }
    }
    
    public class UnionFind {
        var parent: [Int]
        var count: Int
        
        public init(_ m: Int, _ n: Int, _ grid: [[Character]]) {
            self.count = 0
            for i in 0..<m {
                for j in 0..<n {
                    if grid[i][j] == "1" {
                        self.count += 1
                    }
                }
            }
            
            self.parent = [Int](repeatElement(0, count: m * n))
            for i in 0..<(m * n) {
                self.parent[i] = i
            }
        }
        
        public func find(_ p: Int) -> Int {
            var p = p
            while p != self.parent[p] {
                self.parent[p] = self.parent[self.parent[p]]
                p = self.parent[p]
            }
            return p
        }
        
        public func getCount() -> Int {
            return self.count
        }
        
        public func connected(_ p: Int, _ q: Int) -> Bool {
            return find(p) == find(q)
        }
        
        public func union(_ p: Int, _ q: Int) {
            let i = find(p)
            let j = find(q)
            
            if i == j {
                return
            }
            self.parent[i] = j
            self.count -= 1
        }
    }
    

Log in to reply
 

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