[Swift]LeetCode752. 打开转盘锁 | Open the Lock

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10529534.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009". 

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck. 

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1 

Note:

1. The length of deadends will be in the range [1, 500].
2. target will not be in the list deadends.
3. Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

---

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。 

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1 

提示：

1. 死亡列表 deadends 的长度范围为 [1, 500]。
2. 目标数字 target 不会在 deadends之中。
3. 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

---

Runtime: 296 ms

Memory Usage: 20.1 MB

class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        var start: Set<String> = []
        var end: Set<String> = []
        let deadends: Set<String> = Set(deadends)
        
        var startToNow: Set<String> = []
        var endToNow: Set<String> = []

        start.insert("0000")
        end.insert(target)
        
        startToNow.insert("0000")
        endToNow.insert(target)
        
        var steps = 0
        
        // Tip: Start from both sides
        while !start.isEmpty && !end.isEmpty {
            var temp: Set<String> = []
                        
            if !start.intersection(end).isEmpty {
                return steps
            }
            
            for s in start {
                if deadends.contains(s) { continue }
                
                for next in getNext(s) {
                    if !deadends.contains(next) && !startToNow.contains(next) {
                        temp.insert(next)
                    }
                }
            }
            steps += 1
            
            (start, end) = (end, temp)
            (startToNow, endToNow) = (endToNow, startToNow.union(temp))
        }
        
        return -1
    }
    
    private func getNext(_ s: String) -> Set<String> {
        var s: [Int] = Array(s).map{ return Int(String($0))! }
        var res: Set<String> = []
        
        for i in  0 ..< 4 {
            var t = s
            t[i] = (s[i] + 1) % 10
            res.insert(t.reduce("", { return $0 + String($1) }))
            t[i] = (s[i] - 1 + 10) % 10
            res.insert(t.reduce("", { return $0 + String($1) }))
        }
        return res
    }
}

---

560ms

class Solution {
    struct Value: Hashable, CustomStringConvertible {
        let v1: Int
        let v2: Int
        let v3: Int
        let v4: Int

        init(v1: Int, v2: Int, v3: Int, v4: Int) {
            self.v1 = v1
            self.v2 = v2
            self.v3 = v3
            self.v4 = v4
        }

        init(value: Int) {
            let digits = Value.convertToDigits(number: value)

            self.init(v1: digits[0], v2: digits[1], v3: digits[2], v4: digits[3])
        }

        var nextValues: [Value] {
            return [
                Value(v1: v1.incrementDecimal(), v2: v2, v3: v3, v4: v4),
                Value(v1: v1.decrementDecimal(), v2: v2, v3: v3, v4: v4),
                Value(v1: v1, v2: v2.incrementDecimal(), v3: v3, v4: v4),
                Value(v1: v1, v2: v2.decrementDecimal(), v3: v3, v4: v4),
                Value(v1: v1, v2: v2, v3: v3.incrementDecimal(), v4: v4),
                Value(v1: v1, v2: v2, v3: v3.decrementDecimal(), v4: v4),
                Value(v1: v1, v2: v2, v3: v3, v4: v4.incrementDecimal()),
                Value(v1: v1, v2: v2, v3: v3, v4: v4.decrementDecimal()),
            ]
        }

        var description: String {
            return "(v1)(v2)(v3)(v4)"
        }

        private static func convertToDigits(number: Int) -> [Int] {
            let first = number % 10
            let second = (number % 100) / 10
            let third = (number % 1000) / 100
            let fourth = (number % 10000) / 1000

            return [fourth, third, second, first]
        }
    }

    class Combination: Hashable {
        let value: Value
        let step: Int

        init(value: Value, step: Int) {
            self.value = value
            self.step = step
        }

        var hashValue: Int {
            return value.hashValue
        }

        static func == (lhs: Solution.Combination, rhs: Solution.Combination) -> Bool {
            return lhs.value == rhs.value
        }
    }

    private var queue: [Combination] = []
    private var queuedValues: Set<Value> = []

    func openLock(_ deadends: [String], _ target: String) -> Int {
        let convertedDeadends = deadends.map { Int($0)! }
        let convertedTarget = Int(target)!

        return openLock(convertedDeadends, convertedTarget)
    }

    private func openLock(_ deadends: [Int], _ target: Int) -> Int {
        let initialCombination = Combination(value: Value(value: 0), step: 0)
        let targetValue = Value(value: target)
        let deadendValues = Set(deadends.map { Value(value: $0) })

        queue.append(initialCombination)

        while !queue.isEmpty {
            let combination = queue.removeFirst()

            guard !deadendValues.contains(combination.value) else { continue }
            if combination.value == targetValue {
                return combination.step
            }

            enqueuePossibleCombinations(from: combination)
        }

        return -1
    }

    private func enqueuePossibleCombinations(from combination: Combination) {
        let nextStep = combination.step + 1

        combination.value.nextValues.forEach {
            enqueueIfPossible(value: $0, step: nextStep)
        }
    }

    private func enqueueIfPossible(value: Value, step: Int) {
        guard !queuedValues.contains(value) else { return }
        queuedValues.insert(value)

        let combination = Combination(value: value, step: step)
        queue.append(combination)
    }
}

extension Int {
    func incrementDecimal() -> Int {
        return (self + 1) % 10
    }

    func decrementDecimal() -> Int {
        return (self - 1 + 10) % 10
    }
}

---

696ms

final class Solution {
    
    func openLock(_ deadends: [String], _ target: String) -> Int {
        let deadends = Set(deadends.map { str in
            Array(str).map { Int(String($0))! }
        })
        let target = Array(target).map { Int(String($0))! }
        let start = [0, 0, 0, 0]
        var q = Queue<[Int]>()
        var visited = Set<[Int]>()
        q.push(start)
        visited.insert(start)
        var count = 0
        while !q.isEmpty {
            let size = q.size
            for i in 0..<q.size {
                let node = q.pop()
                if deadends.contains(node) { continue }
                if target == node { return count }
                for (i, digit) in node.enumerated() {
                    var neighbor = node
                    neighbor[i] = (digit + 1) % 10
                    if !visited.contains(neighbor) {
                        q.push(neighbor)
                        visited.insert(neighbor)
                    }
                    neighbor = node
                    neighbor[i] = (digit - 1)
                    if neighbor[i] == -1 { neighbor[i] = 9 }
                    if !visited.contains(neighbor) {
                        q.push(neighbor)
                        visited.insert(neighbor)
                    }
                }
            }
            count += 1
        }
        return -1
    }
}

struct Queue<T> {
    var arr = [T]()
    var head = 0
    
    mutating func push(_ val: T) {
        arr.append(val)
    }
    
    mutating func pop() -> T {
        let res = arr[head]
        head += 1
        return res
    }
    
    var isEmpty: Bool {
        return head >= arr.count
    }
    
    var size: Int {
        return arr.count - head
    }
}

---

704ms

typealias Combo = [Int]

class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        let target = Array(target).compactMap {Int(String($0)) }
        let start = [0,0,0,0]
        var seen = Set<Combo>()

        for word in deadends {
            seen.insert(Array(word).map { Int(String($0))! })
        }
        guard !seen.contains(start) else { return -1 }
        var q: [Combo] = [start]
        var level = 0

        while !q.isEmpty {
            
            var tempQ: [Combo] = []
            for current in q {
                guard current != target else { return level }
                seen.insert(current) // add to deadends/visited list

                for i in 0 ..< current.count {
                    var nextValue = current
                    nextValue[i].next()

                if !seen.contains(nextValue) {
                    tempQ.append(nextValue)
                    seen.insert(nextValue)
                }

                var prevValue = current
                prevValue[i].prev()

                if !seen.contains(prevValue) {
                    tempQ.append(prevValue)
                    seen.insert(prevValue)
                }
                }
            }
            level += 1
            q = tempQ

        }
        return -1
    }
}

extension Int {
    mutating func next() {
        self = (self + 1) % 10
    }
    mutating func prev() {
        self = (self + 10 - 1) % 10
    }
}

---

772ms

class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        let target = Array(target).map{ Int("($0)")! }
        let deadends = Set(Array(deadends).map{ $0.map{ Int("($0)")! } })
        var visited = Set<[Int]>()
        var queue = [([0,0,0,0], 0)]
        var i = 0
        while i != queue.count {
            let (candidate, index) = queue[i]
            i += 1
            if visited.contains(candidate) || deadends.contains(candidate) { continue }
            if candidate == target { return index }
            visited.insert(candidate)
            for j in 0...3 {
                var c = candidate
                c[j] = (c[j] + 1) % 9
                 queue.append((c, index+1))
            }
            for j in 0...3 {
                var c = candidate
                c[j] = c[j] == 0 ? 9 : c[j] - 1
                queue.append((c, index+1))
            }
            if i > 100000 { return -10000}
        }
        return -1
    }
}

---

784ms

class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        let target = Array(target).map{ Int("($0)")! }
        let deadends = Set(Array(deadends).map{ $0.map{ Int("($0)")! } })
        var visited = Set<[Int]>()
        var queue = [([0,0,0,0], 0)]
        var i = 0
        while i != queue.count {
            let (candidate, index) = queue[i]
            i += 1
            if visited.contains(candidate) || deadends.contains(candidate) { continue }
            if candidate == target { return index }
            visited.insert(candidate)
            for j in 0...3 {
                var c = candidate
                var cj = c[j]
                c[j] = (cj + 1) % 9
                queue.append((c, index+1))
                c[j] = cj == 0 ? 9 : cj - 1
                queue.append((c, index+1))
            }
        }
        return -1
    }
}

---

Runtime: 864 ms

Memory Usage: 20.3 MB

class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        var deadlock:Set<String> = Set<String>(deadends)
        if deadlock.contains("0000")
        {
            return -1
        }
        var res:Int = 0
        var visited:Set<String> = ["0000"]
        var q:[String] = ["0000"]
        while(!q.isEmpty)
        {
            res += 1
            for k in stride(from:q.count,to:0,by:-1)
            {
                let t:String = q.removeFirst()
                let arrChar:[Character] = Array(t)
                let arrInt:[Int] = arrChar.map{$0.ascii}
                for i in 0..<t.count
                {
                    var c:Character = arrChar[i]
                    var num:Int = arrInt[i]
                    var str1:String = t.subString(0, i) + String(c == "9" ? 0 : num - 48 + 1) + t.subString(i + 1)
                    var str2:String = t.subString(0, i) + String(c == "0" ? 9 : num - 48 - 1) + t.subString(i + 1)
                    if str1 == target || str2 == target
                    {
                        return res
                    }
                    if !visited.contains(str1) && !deadlock.contains(str1)
                    {
                        q.append(str1)
                    }
                    if !visited.contains(str2) && !deadlock.contains(str2)
                    {
                        q.append(str2)
                    }
                    visited.insert(str1)
                    visited.insert(str2)                    
                }                
            }
        }
        return -1
    }
}

//Character扩展 
extension Character  
{  
  //Character转ASCII整数值(定义小写为整数值)
   var ascii: Int {
       get {
           return Int(self.unicodeScalars.first?.value ?? 0)
       }       
    }    
}

extension String {
    // 截取字符串：指定索引和字符数
    // - begin: 开始截取处索引
    // - count: 截取的字符数量
    func subString(_ begin:Int,_ count:Int) -> String {
        let start = self.index(self.startIndex, offsetBy: max(0, begin))
        let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
        return String(self[start..<end]) 
    }
    
    // 截取字符串：从index到结束处
    // - Parameter index: 开始索引
    // - Returns: 子字符串
    func subString(_ index: Int) -> String {
        let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
        return String(self[theIndex..<endIndex])
    }
}