Simple and Concise C++ ,using DFS


  • 0
    J
    class Solution {
    public:
    
        unordered_map<string, unordered_map<string,double>>  table;  // the graph
        vector<double>  res;
    
        double dfs(string a, string b,  unordered_set<string>& used){ 
            if(table.find(a) == table.end())        return -1.0;
            if(table[a].find(b) != table[a].end())  return table[a][b];
            
            used.insert(a);
            for(auto &p : table[a]){
                if(used.find(p.first) == used.end()){
                    double tmp =  dfs(p.first,b,used);
                    if(tmp > 0) return p.second * tmp;   
                }
            }
            return -1.0;
        }
    
    
        vector<double> calcEquation(vector<pair<string, string>> equations, 
        vector<double>& values, vector<pair<string, string>> queries) {
            // 1. build the graph
            for(int i = 0; i!= values.size();++i){
                string a = equations[i].first, b = equations[i].second;
                table[a].insert(make_pair(b,values[i]));
                if(values[i] != 0)  
                table[b].insert(make_pair(a,1.0/values[i]));
            }
      
            // 2. using dfs to search the value
            for(auto &q : queries){
                unordered_set<string>   used;
                double tmp = dfs(q.first,q.second,used);
                if(tmp > 0) res.push_back(tmp);
                else    res.push_back(-1.0);
            }
            return res;
        }
    
    
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.