Evaluate Division (Leetcode 399)

参考: http://www.cnblogs.com/grandyang/p/5880133.html

G家的一道面试题。这道题相当于weighted graph。用adjacency matrix会好，然而vector<256, vector<256, 0>> 这种方法不便于搜索。于是用unordered_map, 建立类似于adjacency list的adj matrix。

BFS:

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
 
        vector<double> ret;
        unordered_map<string, vector<pair<string, double>>> adj;
        for(int i=0; i<equations.size(); i++){
            adj[equations[i].first].push_back({equations[i].second, values[i]});
            adj[equations[i].second].push_back({equations[i].first, 1.0/values[i]});
        }
   
        for(int i=0; i<queries.size(); i++){
            if(!adj.count(queries[i].first)){
                ret.push_back(-1.0);
                continue;
            }
            bool isFound = false;
            queue<pair<string, double>> q;
            unordered_set<string> st;
            q.push({queries[i].first, 1.0});
            st.insert(queries[i].first);
            
            while(!q.empty()){
                string cur = q.front().first;
                double ratio = q.front().second; 
                q.pop();
                if(cur == queries[i].second){
                    isFound = true;
                    ret.push_back(ratio);
                    break;
                }
                for(auto it : adj[cur]){
                    if(st.count(it.first)) continue;
                    st.insert(it.first);
                    q.push({it.first, ratio * it.second});
                }
            }
            if(!isFound) ret.push_back(-1.0);
        }
        return ret;
    }
};

有了BFS，可以照着写出DFS。
DFS:

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        for(int i=0; i<equations.size(); i++){
            mp[equations[i].first].push_back({equations[i].second, values[i]});
            mp[equations[i].second].push_back({equations[i].first, 1.0/values[i]});
        }
        
        vector<double> ret;
        for(auto it : queries){
            if(!mp.count(it.first) || !mp.count(it.second)){
                ret.push_back(-1.0);
                continue;
            }
            else{
                unordered_set<string> st;
                st.insert(it.first);
                double temp = dfs(st, it.first, it.second, 1.0);
                ret.push_back(temp);
            }
        }
        return ret;
    }
    
    double dfs(unordered_set<string> &st, string start, string dest, double ratio){
        if(start == dest){
            return ratio;
        }
        for(auto it : mp[start]){
            if(st.count(it.first)){
                continue;
            }
            st.insert(it.first);
            double result = dfs(st, it.first, dest, ratio * it.second);
            if(result != -1.0) return result;
        }
        return -1.0;
        
    }
private:
    unordered_map<string, vector<pair<string, double>>> mp;
};