3MS C++ solution using DFS easy to follow


  • 0
    G
    class Solution {
    public:
    
        
        bool Get(const string &From, const string &To,unordered_map<string,map<string,double> > &M,unordered_set<string> &Visited,double &Insert)
        {
            if(From == To)
            {
                return (true);
            }
            
            if(Visited.find(From) != Visited.end())
            {
                return (false);
            }
            
            Visited.insert(From);
            
            for(auto &P :M[From])
            {
                double I = Insert * P.second;
                
                if(Get(P.first,To,M,Visited,I) == true)
                {
                    Insert = I;
                    return (true);
                }
            }
            
            return (false);
        }
    
        
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) 
        {
            unordered_map<string,map<string,double> > M;
            vector<double> Res;
            
            int i = 0;
            
    
            for(auto &P : equations)
            {
                M[P.first].insert(make_pair(P.second,values[i]));
                M[P.second].insert(make_pair(P.first,1.0/values[i]));
                i++;
            }
            
            for(auto &P : queries)
            {
                unordered_set<string> Visited;
                
                if(M.find(P.first) == M.end())
                {
                    Res.push_back(-1);
                    continue;
                }
                
                if(M[P.first].find(P.second) != M[P.first].end())
                {
                    Res.push_back(M[P.first][P.second]);
                    continue;
                }
                
                double Insert = 1.0;
                
                if(Get(P.first,P.second,M,Visited,Insert))
                {
                    Res.push_back(Insert);
                }
                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.