DFS, BFS - Swift


  • 0
    class Solution {
        func flipLights_BFS(_ n: Int, _ m: Int) -> Int {
            if n <= 0 || m <= 0 {
                return 1
            }
            
            let status = [String](repeatElement("1", count: n))
            var queue = [[String]]()
            var level = 0
            var result = 0
            
            queue.append(status)
            while !queue.isEmpty {
                let count = queue.count
                var visited = Set<String>()
                level += 1
                for _ in 0..<count {
                    let status = queue.removeFirst()
                    let statusArray = [action1(status), action2(status), action3(status), action4(status)]
                    
                    for status in statusArray {
                        if !visited.contains(status.joined()) {
                            if level != m {
                                queue.append(status)
                            }
                            visited.insert(status.joined())
                        }
                    }
                    
                    if level == m {
                        result = visited.count
                    }
                }
            }
            
            return result
        }
        
        func flipLights_DFS(_ n: Int, _ m: Int) -> Int {
            if n <= 0 || m <= 0 {
                return 1
            }
            
            let status = [String](repeatElement("1", count: n))
            var kinds = Set<String>()
            var cache = Set<String>()
            
            helper(m, status, &kinds, &cache)
            
            return kinds.count
        }
        
        private func helper(_ remain: Int, _ status: [String], _ kinds: inout Set<String>, _ cache: inout Set<String>) {
            if remain == 0 {
                kinds.insert(status.joined())
                return
            }
            
            let statusArray = [action1(status), action2(status), action3(status), action4(status)]
            
            for status in statusArray {
                if !cache.contains("\(remain)_\(status.joined())") {
                    helper(remain - 1, status, &kinds, &cache)
                    cache.insert("\(remain)_\(status.joined())")
                }
            }
        }
        
        private func action1(_ status: [String]) -> [String] {
            var result = [String]()
            
            for i in 0..<status.count {
                result.append(flip(status[i]))
            }
            
            return result
        }
        
        private func action2(_ status: [String]) -> [String] {
            var result = [String]()
            
            for i in 0..<status.count {
                if (i + 1) % 2 == 0 {
                    result.append(flip(status[i]))
                } else {
                    result.append(status[i])
                }
            }
            
            return result
        }
        
        private func action3(_ status: [String]) -> [String] {
            var result = [String]()
            
            for i in 0..<status.count {
                if (i + 1) % 2 == 1 {
                    result.append(flip(status[i]))
                } else {
                    result.append(status[i])
                }
            }
            
            return result
        }
        
        private func action4(_ status: [String]) -> [String] {
            var result = [String]()
            
            for i in 0..<status.count {
                if (i + 1) % 3 == 1 {
                    result.append(flip(status[i]))
                } else {
                    result.append(status[i])
                }
            }
            
            return result
        }
        
        private func flip(_ status: String) -> String {
            return status == "1" ? "0" : "1"
        }
    }
    

Log in to reply
 

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