Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

👨‍💻 Алгоритм:

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

3⃣Обработка запросов:
Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса.

😎 Решение:

class Solution {
    func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
        var graph = [String: [String: Double]]()

        for (i, equation) in equations.enumerated() {
            let A = equation[0], B = equation[1]
            let value = values[i]
            graph[A, default: [String: Double]()][B] = value
            graph[B, default: [String: Double]()][A] = 1.0 / value
        }

        func bfs(_ start: String, _ end: String) -> Double {
            guard let _ = graph[start], let _ = graph[end] else { return -1.0 }
            var queue = [(start, 1.0)]
            var visited = Set<String>()
            
            while !queue.isEmpty {
                let (current, curProduct) = queue.removeFirst()
                if current == end { return curProduct }
                visited.insert(current)
                for (neighbor, value) in graph[current, default: [String: Double]()] {
                    if !visited.contains(neighbor) {
                        queue.append((neighbor, curProduct * value))
                    }
                }
            }
            return -1.0
        }

        var results = [Double]()
        for query in queries {
            let C = query[0], D = query[1]
            results.append(bfs(C, D))
        }
        return results
    }
}

Ставь 👍 и забирай 📚 Базу знаний