Evaluate Division Problem


Description

LeetCode Problem 399.

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries[j] = [C_j, D_j] represents the j^th query where you must find the answer for C_j / D_j = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

1
2
3
4
5
6
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]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

1
2
Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

1
2
Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= A_i.length, B_i.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= C_j.length, D_j.length <= 5
  • A_i, B_i, C_j, D_j consist of lower case English letters and digits.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    unordered_map<string, vector<pair<string, double>>> graph;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            string a = equations[i][0];
            string b = equations[i][1];
            double val = values[i];
            
            graph[a].push_back({b, val});
            graph[b].push_back({a, (double)1/val});
        }
        
        vector<double> result;
        for (auto query : queries) {
            unordered_set<string> visited;
            result.push_back(dfs(query[0], query[1], visited));
        }
        return result;
    }
    
    double dfs(string src, string dst, unordered_set<string> &visited) {
        if (graph.find(src) == graph.end()) return -1;
        if (src == dst) return 1;
        
        for (auto node : graph[src]) {
            if (visited.count(node.first)) continue;
            visited.insert(node.first);
            double res = dfs(node.first, dst, visited);
            if (res != -1) return res * node.second;
        }
        return -1;
    }
};




Related Posts

1-Bit And 2-Bit Characters Problem

LeetCode 717. We have two special characters, the first character...

Teemo Attacking Problem

LeetCode 495. Our hero Teemo is attacking an enemy Ashe...

Range Addition II Problem

LeetCode 598. You are given an m x n matrix...

Max Consecutive Ones Problem

LeetCode 485. Given a binary array nums, return the maximum...

132 Pattern Problem

LeetCode 456. Given an arrayof n integers nums, a 132...

Summary Ranges Problem

LeetCode 228. You are given a sorted unique integer array...