算法

(DFS)

这个题目实在是太好了，感觉非常灵活，有变通性，直接想题目感觉根本不会想到 dfs的解法，但是后来理清思路了以后就发现其实是在一个图里面找是否存在这个路径，并且要把这个路径的距离返回，我的code 里面夹杂了我在写这个题目的思考过程，期间有想放弃看答案的时候，还好”观世音菩萨”加持住了，哈哈哈，忍住了没有看答案，最后还是自己写出来了。

时间复杂度分析：我先把这个时间复杂度分析留在这里，明天早上起来看看，因为我现在好困啊。

C++ 代码

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        // 感觉就是dfs 的题目，好久没有做dfs了啊
        // 感觉就是找一条从起点到终点的路啊
        // 一条路一直走下去，如果走不下去的时候，就回头，回到上一次做选择的地方，再走其他的路。
        // 感觉就是这样做，这道题目
        // 怎么写呢，这道题目
        // 这个unordered_map 不行，怎么办呢？ 用什么可以替换呢？
        // 好困啊，求观世音菩萨加持，让我把这个题目想出来
        unordered_map<string, double> map;
        unordered_map<string, vector<string>> start2end;
        // avoid loop


        for (int i = 0; i < equations.size(); i++) {

            string start = equations[i].first;
            string end = equations[i].second;


            map[start + end] = values[i];
            map[end + start] = 1.0/values[i];  

            start2end[start].push_back(end);
            start2end[end].push_back(start);
        }
        // define a return vector to store the result
        vector<double> res;
        // map 存好了以后就可以进行dfs
        for (int i = 0; i < queries.size(); i++) {
            unordered_set<string> visited;
            pair<string, string> curQuery = queries[i];
            // 怎么进行dfs 呢？
            // 首先需要 我们要找的路劲的起点和终点， 那我只需要定义一个起点和一个终点就好了啊
            string start = curQuery.first;
            string end = curQuery.second;
            // 知道起点和终点以后，我们就可以在我们存好的　hashmap 里面进行dfs了
            // 我觉得这道题目真的很好
            // 一开始把query 的结果定义为没有，直到找到以后再重新赋值
            double value = 1;
            value = dfs(start, end, map, start2end, value, visited);
            res.push_back(value);
        }
        return res;
        // unordered_map 里面应该怎么写， 当 a 走到 b 之后， b 不能再走回 a 了。 
        // 要怎么才可以消环呢？



    }
private:
    double dfs(string start, string end, unordered_map<string, double>& map, unordered_map<string, vector<string>>& start2end, double value, unordered_set<string>& visited)  {
        // the key here should be start, should not be the pair of the start and the end
        // in that way, we can query the hashmap if the start point exist in this map
        // however, how can I store both end point string and the double value into a single mapped value?
        //   观世音菩萨加持
        // 对啊，一个hashmap 存不下的时候就用两个hashmap 嘛
        //  在unordered_map里面走过一个就要erase 一个

        if (!start2end.count(start)) {
            return -1.0;
        } else {
            if (start == end) {
                return value;
            }
            // 不行我一定要自己写出来，不要看答案
            // 观世音菩萨加持 感觉这里应该是multimap, 而不是 unordered_map, 
            vector<string> nexts = start2end[start];
            visited.insert(start);
            for (int i = 0; i < nexts.size(); i++) {
                string next = nexts[i];
                if (visited.count(next)) {
                    continue;
                }
                // 观世音菩萨加持
                //pair<string, string> cur = make_pair(start, next);

                double tmp = dfs(next, end, map, start2end, value*map[start+next], visited);
                if (tmp > -1.0) {
                    return tmp;
                }
                visited.erase(start);
            }
            return -1.0;
            // 求观世音菩萨加持，让我把最后一个bug de 出来

        }

    }
};