C++ DFS solution


  • 0
    J

    firstly I defined one node to hold string and double value, like node. using the hash map to save all possible state transition. using the DFS algorithm to find the path from source to destination.

    class Solution {
    public:
    struct node
    {
        string str;
        double d;
        node(string _str,double _d)
        {
            str = _str;d = _d;
        }
    };
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            unordered_map<string,vector<node>> map;
            for(int i = 0;i<equations.size();i++)
            {
                string first = equations[i].first;
                string second = equations[i].second;
                map[first].push_back(node(second,values[i]));
                map[second].push_back(node(first,1/values[i]));
            }
            
            vector<double>res;
            for(auto query:queries)
            {
                string src = query.first;
                string dst = query.second;
                double result = 1.0;
                unordered_set<string> set;
                if(dfs(src,dst,map,set,result)) res.push_back(result);
                else res.push_back(-1.0);
            }
            return res;
        }
    private:
        bool dfs(string src,string dst,unordered_map<string,vector<node>>&map,unordered_set<string>&set,double &result)
        {
            if(map.find(src)==map.end()) return false; //make sure string is the dictionary
            if(set.find(src)!=set.end()) return false; //visited before.
            set.insert(src); //make source as visited
            if(src.compare(dst)==0)return true; //found return
           
            vector<node> next_string = map[src];
            for(int i = 0;i<next_string.size();i++)
            {
                result = result*next_string[i].d;
                if(dfs(next_string[i].str,dst,map,set,result)) return true;
                result = result/next_string[i].d;
            }
            return false;
        }
    };
    

Log in to reply
 

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