Straightforward C++ solution using hashmap and DFS, although a little long, 0ms


  • 0
    S
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries){
            unordered_map<string, int> vertex;
            vector<vector<double>> edges;
            buildgraph(vertex, edges, equations, values);
            vector<double> result;
            for(auto c: queries){
                if(vertex.find(c.first) == vertex.end() || vertex.find(c.second) == vertex.end()){
                    result.push_back(-1.0);
                    continue;
                }
                bool flag = false;
                vector<bool> used(vertex.size(), false);
                double curresult = query(edges, vertex[c.first], vertex[c.second], 1.0, &flag, used);
                if(flag){
                    result.push_back(curresult);
                }
                else{
                    result.push_back(-1);
                }
            }
            return result;
        }
        
        void buildgraph(unordered_map<string, int> &vertex, vector<vector<double>> &edges, vector<pair<string, string>> &equations, vector<double>& values){
            for(int i = 0, j = 0; j < equations.size(); j++){
                if(vertex.find(equations[j].first) == vertex.end()){
                    vertex[equations[j].first] = i;i++;
                }
                if(vertex.find(equations[j].second) == vertex.end()){
                    vertex[equations[j].second] = i;i++;
                }
            }
            
            edges.assign(vertex.size(), vector<double>(vertex.size(),-1.0));
            for(int i = 0; i<vertex.size(); i++){
                edges[i][i] = 1.0;
            }
            for(int j = 0; j<equations.size(); j++){
                edges[vertex[equations[j].first]][vertex[equations[j].second]] = values[j];
                edges[vertex[equations[j].second]][vertex[equations[j].first]] = 1.0/values[j];
            }
                
            return;
        }
        
        double query(vector<vector<double>> &edges, int first, int second, double value, bool *flag, vector<bool> &used){
            if(first == second){
                *flag = true;
                return value;
            }
            used[first] = true;
            for(int i = 0; i < edges.size(); i++){
                if(!used[i] && edges[first][i] > 0){
                    value *= edges[first][i];
                    value = query(edges, i, second, value, flag, used);
                    if(*flag){
                        break;
                    }
                    value /= edges[first][i];
                }
            }
            used[first] = false;
            return value;
        }
    };

Log in to reply
 

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