C++ easy understanding dfs 3ms solution with adjaction list


  • 0
    N

    I think using BFS can be faster, but you need to make a Node structure to store the previous result inside the queue

    class Solution {
    private:
        unordered_map<string, vector<pair<string, double> > > mapper;
        unordered_set<string> visit;
        double thisOne = 0;
        void dfs (string start, string endT, double val) {
            if (start == endT) {
                thisOne = val;
                return;
            }
            
            vector<pair<string, double> > temps = mapper[start];
            
            for (auto tmp : temps) {
                if (visit.find(tmp.first) == visit.end()) {
                    visit.insert(tmp.first);
                    dfs(tmp.first, endT, val * tmp.second);
                }
                if (thisOne)
                    break; 
            }
        }
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            vector<double> answer(queries.size());
            for (int i = 0; i < equations.size(); i++) {
                mapper[equations[i].first].push_back(make_pair(equations[i].second, values[i]));
                mapper[equations[i].second].push_back(make_pair(equations[i].first, 1.0 / values[i]));
            }
            
            for (int i = 0; i < queries.size(); i++) {
                visit.clear();
                string start = queries[i].first;
                string endT = queries[i].second;
                thisOne = 0;
                if (mapper.find(start) == mapper.end() || mapper.find(endT) == mapper.end())
                    answer[i] = -1.0;
                else {
                    visit.insert(start);
                    dfs(start, endT, 1.0);
                    if (thisOne)
                        answer[i] = thisOne;
                    else
                        answer[i] = -1;
                }
            }
            
            return answer;
        }
    };
    

Log in to reply
 

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