Share my C++ BFS solution


  • 0
    B
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string> > query) {
            vector<double> res;
            unordered_map<string, vector<int>> map;
            int n_equ = (int) equations.size();
            for(int i = 0; i < n_equ; i++) {
                map[equations[i].first].push_back(i);
                if(equations[i].second != equations[i].first) {
                    map[equations[i].second].push_back(i);
                }
            }//just use the map to store the indices
            
            for(auto item:query) {
                res.push_back(bfs(item, map, equations, values));
            }
            return res;
        }
        
    private:
        double bfs(const pair<string, string>& query,  unordered_map<string, vector<int>>& map, const vector<pair<string, string>>& equations, const vector<double>& values) {
            queue<pair<string, double>> q;
            bool found = false;
            unordered_set<string> visited;
            q.push({query.first, 1.0});
            while(!q.empty() && !found) {
                    auto cur = q.front();
                    q.pop();
                    if(map.find(cur.first) == map.end()) continue;
                    visited.insert(cur.first);
                    if(cur.first == query.second) {
                        found = true;
                        return cur.second;
                    }
                    vector<int> next = map[cur.first];
                    for(int index:next) {
                        pair<string, double> ins;
                        if(equations[index].first == cur.first) {
                            if(visited.find(equations[index].second) != visited.end()) continue;
                            ins = make_pair(equations[index].second, values[index] * cur.second);
                        }
                        else {
                            if(visited.find(equations[index].first) != visited.end()) continue;
                            ins = make_pair(equations[index].first, cur.second/values[index]);
                        }
                        q.push(ins);
                    }
            }
            return -1.0;
        }
        
    };

Log in to reply
 

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