Leetcode 399. Evaluate Division

Posted on | In |

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
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 ].

The input is: vector<pair<string, string>> equations,

vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ [“a”, “b”], [“b”, “c”] ],

values = [2.0, 3.0],

queries = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].

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

思路

dfs

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
37
38
39
40
41
42
43
44
struct node{
    string num;
    double v;
    node(string nn,double vv):num(nn),v(vv){}
};
class Solution {
public:
    map<string,vector<node> >g;
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        set<string> ss;
        for(int i=0;i<equations.size();i++){
            pair<string,string> p=equations[i];
            g[p.first].push_back(node(p.second,values[i]));
            g[p.second].push_back(node(p.first,1/values[i]));           
        }
        vector<double> answer;
        set<string> vis;
        for(auto b:queries)
        {
            vis.clear();
            
         if(!g.count(b.first)&&!g.count(b.second)) answer.push_back(-1);
          else answer.push_back(dfs(b.first,b.second,vis));
            
        }
        return answer;
    }
    double dfs(string cur,string target,set<string> &vis){
        if(cur==target) {
            return 1;
        }
        vis.insert(cur);
        for(int i=0;i<g[cur].size();i++){
            node t=g[cur][i];
            if(!vis.count(t.num)) {
               double d=dfs(t.num,target,vis);//!!
          if(d>0) return t.v*d;
            }
        }
        return -1;
       
    }
    
};

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct node{
    string num;
    double v;
    node(string nn,double vv):num(nn),v(vv){}
};
class Solution {
public:
    map<string,vector<node> >g;
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        set<string> ss;
        for(int i=0;i<equations.size();i++){
            pair<string,string> p=equations[i];
            g[p.first].push_back(node(p.second,values[i]));
            g[p.second].push_back(node(p.first,1/values[i]));
            ss.insert(p.first);
            ss.insert(p.second);            
        }
        vector<double> answer;
        set<string> vis;
        for(auto b:queries)
        {
            vis.clear();
            double ans=1;
         if(!ss.count(b.first)&&!ss.count(b.second)) answer.push_back(-1);
         else if(!dfs(b.first,b.second,vis,ans,answer)) answer.push_back(-1);
            
        }
        return answer;
    }
    bool dfs(string cur,string target,set<string> &vis,double &ans,vector<double> &answer){
        if(vis.count(cur)) return false;
        if(cur==target) {
            answer.push_back(ans);
            return true;
        }
        vis.insert(cur);
        for(int i=0;i<g[cur].size();i++){
            node t=g[cur][i];
            if(!vis.count(t.num)) {
           double tmp=ans*t.v;                
            if(dfs(t.num,target,vis,tmp,answer)) return true;
            }
            
        }
        
        return false;
       
    }
    
};