399.evaluate-division.md

399. Evaluate Division

TODO: Review the notes + implementations

Traversal

We can model the problem as graph problem, all the symbols become the vertex, and for equation a / b = 2.0, it will be the edge a to b with 2.0 weight and b to a with 1 / 2.0 weight. Then we search the graph for all queries.

data class Node(
    val value: Double,
    val symbol: String
)

class Solution {
    fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
        val graph = buildGraph(equations, values)
        val results = DoubleArray(queries.size)
        
        for (i in 0 until queries.size) {
            val query = queries[i]
            val source = query[0]
            var target = query[1]
            if (!graph.containsKey(source) || !graph.containsKey(target)) {
                results[i] = -1.0
                continue
            }
            if (source == target) {
                results[i] = 1.0
                continue
            }
            val visited = hashSetOf<String>()
            results[i] = dfs(graph, source, target, 1.0, visited)
            // bfs(graph, source, target)
        }
        return results
    }

    private fun buildGraph(equations: List<List<String>>, values: DoubleArray): HashMap<String, HashSet<Node>> {
        val graph = hashMapOf<String, HashSet<Node>>()
        for (i in 0 until equations.size) {
            val source = equations[i][0]
            val target = equations[i][1]
            val value = values[i]
            
            if (!graph.containsKey(source)) graph[source] = hashSetOf<Node>()
            if (!graph.containsKey(target)) graph[target] = hashSetOf<Node>()
            graph[source]!!.add(Node(value, target))
            graph[target]!!.add(Node(1.0 / value, source))
        }
        return graph
    }
    
    private fun bfs(graph: HashMap<String, HashSet<Node>>, source: String, target: String): Double {
        val visited = hashSetOf<String>()
        val queue = ArrayDeque<Pair<String, Double>>()
        queue.addLast(source to 1.0)
        while (queue.isNotEmpty()) {
            val pair = queue.removeLast()
            val symbol = pair.first
            val value = pair.second
            if (visited.contains(symbol)) continue
            if (symbol == target) {
                return value
            }
            visited.add(symbol)
            graph[symbol]?.forEach { adj ->
                if (!visited.contains(adj.symbol)) {
                    queue.addLast(adj.symbol to (adj.value * value))
                }
            }
        }
        return -1.0
    }
    
    private fun dfs(graph: HashMap<String, HashSet<Node>>, source: String, target: String, value: Double, visited: HashSet<String>): Double {
        if (visited.contains(source)) return -1.0
        if (source == target) {
            return value
        }
        visited.add(source)
        graph[source]?.forEach { adj ->
            if (!visited.contains(adj.symbol)) {
                val result = dfs(graph, adj.symbol, target, adj.value * value, visited)
                if (result != -1.0) { return result }
            }
        }
        return -1.0
    }
}