剑指 Offer II 111. 计算除法

dfs

class Solution {
    var dict = Dictionary<String,Dictionary<String,Double>>()

    func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
        
        let len = equations.count
        for i in 0..<len {
            let array = equations[i]
            let eq1 = array[0],eq2 = array[1]
            let v  = values[i]
            if dict[eq1] == nil {
                dict[eq1] = [String:Double]()
            }
            dict[eq1]![eq2] = v
            if dict[eq2] == nil {
                dict[eq2] = [String:Double]()
            }
            dict[eq2]![eq1] = 1 / v
        }
        var ans = [Double]()

        for query in queries {
            var visited = [String: Int]()
            ans.append(dfs(query[0], query[1], &visited))
        }
        
            return ans
    }
    
    func dfs(_ start:String, _ end:String,_ visited:inout [String:Int]) -> Double{
        
        guard let value = dict[start] else {
            return -1
        }
        if start == end {
            return 1
        }
        visited[start] = 1
        for tempDict in value {
            if let _ = visited[tempDict.key]{
              continue
            }else{
                let v = dfs(tempDict.key, end, &visited)
                if v >= 0 {
                    return tempDict.value * v
                }
            }
            
        }
        visited.removeValue(forKey: start)
        return -1
        
        
        
        
    }
}