Java AC Solution using graph


  • 63

    Image a/b = k as a link between node a and b, the weight from a to b is k, the reverse link is 1/k. Query is to find a path between two nodes.

        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>();
            HashMap<String, ArrayList<Double>> valuesPair = new HashMap<String, ArrayList<Double>>();
            for (int i = 0; i < equations.length; i++) {
                String[] equation = equations[i];
                if (!pairs.containsKey(equation[0])) {
                    pairs.put(equation[0], new ArrayList<String>());
                    valuesPair.put(equation[0], new ArrayList<Double>());
                }
                if (!pairs.containsKey(equation[1])) {
                    pairs.put(equation[1], new ArrayList<String>());
                    valuesPair.put(equation[1], new ArrayList<Double>());
                }
                pairs.get(equation[0]).add(equation[1]);
                pairs.get(equation[1]).add(equation[0]);
                valuesPair.get(equation[0]).add(values[i]);
                valuesPair.get(equation[1]).add(1/values[i]);
            }
            
            double[] result = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                String[] query = queries[i];
                result[i] = dfs(query[0], query[1], pairs, valuesPair, new HashSet<String>(), 1.0);
                if (result[i] == 0.0) result[i] = -1.0;
            }
            return result;
        }
        
        private double dfs(String start, String end, HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, HashSet<String> set, double value) {
            if (set.contains(start)) return 0.0;
            if (!pairs.containsKey(start)) return 0.0;
            if (start.equals(end)) return value;
            set.add(start);
            
            ArrayList<String> strList = pairs.get(start);
            ArrayList<Double> valueList = values.get(start);
            double tmp = 0.0;
            for (int i = 0; i < strList.size(); i++) {
                tmp = dfs(strList.get(i), end, pairs, values, set, value*valueList.get(i));
                if (tmp != 0.0) {
                    break;
                }
            }
            set.remove(start);
            return tmp;
        }

  • 0
    This post is deleted!

  • 0

    @mzchen
    the reason is i didn't take zero into consideration, because in the problem , it is mentioned the value is positive, not including 0


  • 0

    @helloc93
    Sorry you are right. I didn't notice that statement.


  • 0
    X

    I think if we add the query value back to the graph will become faster.


  • 8
    T

    you dont need to add "set.remove(start);"


  • 0

    said in Java AC Solution using graph:

    Image a/b = k as a link between node a and c, the weight from a to c is k,

    Why a/b relate to c? and a to c is k?


  • 8

    If a/b = 2.0 and b/c = 3.0, we can treat a,b, and c as vertices.
    then edge(a,b) weight 2.0 and edge(b,c) weight 3.0
    backward edge(b,a) weight 1/2.0 and backward edge(c,b)weight 1/3.0
    query a,c is a path from a to c, distance (a,c) = weight(a,b) * weight(b,c)

        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            double[] res = new double[queries.length];
            if(equations.length == 0) return res;
            Map<String, List<Edge>> adjs = new HashMap();
            for(int i=0;i<equations.length;i++){
                String v = equations[i][0];
                String u = equations[i][1];
                Edge ef = new Edge(u, values[i]);
                Edge eb = new Edge(v, 1.0/values[i]);
                if(adjs.containsKey(v)){
                    adjs.get(v).add(ef);
                } else {
                    List<Edge> adjsV = new ArrayList();
                    adjsV.add(ef);
                    adjs.put(v, adjsV);
                }
                if(adjs.containsKey(u)){
                    adjs.get(u).add(eb);
                } else {
                    List<Edge> adjsU = new ArrayList();
                    adjsU.add(eb);
                    adjs.put(u, adjsU);
                }
            }
    
    
            
            for(int i=0;i<queries.length;i++){
                String s = queries[i][0];
                String t = queries[i][1];
                Set<String> visited = new HashSet();
                dfs(adjs,visited, s, t, 1.0,i, res);
                if(res[i] == 0 && s != t) res[i] = -1.0;
            }
    
            return res;
        }
    
        private void dfs(Map<String, List<Edge>> adjs,Set<String> visited, String s, String  t, double distance, int index, double[] res){
            if(s.equals(t)) {
                res[index]  = distance;
            }
            if(visited.contains(s)) return;
            visited.add(s);
            if(!adjs.containsKey(s) || !adjs.containsKey(t)) {
                res[index] = -1.0;
                return;
            }
            List<Edge> adjsV = adjs.get(s);
            Iterator<Edge> iter = adjsV.iterator();
            while(iter.hasNext()){
                Edge e = iter.next();
                dfs(adjs,visited, e.to, t, distance * e.weight,index, res);
            }
        }
    
    class Edge{
            String to;
            double weight;
            Edge(String t, double w){
                to = t;
                weight = w;
            }
        }
    

  • 0

    @hot13399 Thanks for reminding, it is a typo. I have corrected it.


  • 7

    Similar idea here with hashmap inside a hashmap.

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, HashMap<String, Double>> map = new HashMap<String, HashMap<String, Double>>();
            for (int i = 0; i < equations.length; ++i) {
                if (!map.containsKey(equations[i][0]))
                    map.put(equations[i][0], new HashMap<String, Double>());
                if (!map.containsKey(equations[i][1]))
                    map.put(equations[i][1], new HashMap<String, Double>());
                map.get(equations[i][0]).put(equations[i][1], values[i]);
                map.get(equations[i][1]).put(equations[i][0], 1 / values[i]);
            }
            double[] out = new double[queries.length];
            for (int i = 0; i < queries.length; ++i) {
                if (map.containsKey(queries[i][0]) && map.containsKey(queries[i][1])) {
                    if (queries[i][0] == queries[i][1])
                        out[i] = 1.0;
                    else {
                        double judg = dfs(queries[i][0], queries[i][1], new HashSet<String>(), map, 1.0);
                        out[i] = judg == 0.0 ? -1.0 : judg;
                    }
                }
                else out[i] = -1.0;
            }
            return out;
        }
        
        private double dfs(String s, String t, HashSet<String> visited, HashMap<String, HashMap<String, Double>> map, double val) {
            if (map.get(s).containsKey(t)) 
                return val * map.get(s).get(t);
            double tmp = 0.0;
            for (String neighbor : map.get(s).keySet()) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    tmp = dfs(neighbor, t, visited, map, val * map.get(s).get(neighbor));
                    if (tmp != 0.0) break;
                }
            }
            return tmp;
        }
    }
    

  • 0
    K

    I have a question about why we need to use Hashset?


  • 0

    @kate8528577 Because we want to avoid looping the node that we have already visited, otherwise you will get into a cycle and then TLE.


  • 0
    J

    C++ version based on haruhiku's solution.

    class Solution {
    public:
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            vector<double> ans;
            unordered_map<string, unordered_map<string, double>> mp;
            
            for(int i = 0; i < equations.size(); i++) {
                string f = equations[i].first, s = equations[i].second;
                mp[f][s] = values[i];
                mp[s][f] = 1.0 / values[i];
            }
            
            for(int i = 0; i < queries.size(); i++) {
                string f = queries[i].first, s = queries[i].second;
                
                if(mp.count(f) && mp.count(s)) {
                    if(f == s) ans.push_back(1.0);
                    else {
                        unordered_set<string> visited;
                        ans.push_back(dfs(f, s, mp, visited, 1.0));
                    }
                }
                else ans.push_back(-1.0);
            }
            
            return ans;
        }
        
    private:
        double dfs(string f, string s, unordered_map<string, unordered_map<string, double>> &mp, unordered_set<string> &visited, double val) {
            if(mp[f].count(s)) return val * mp[f][s];
            
            for(pair<string, double> p : mp[f]) {
                string str = p.first;
                
                if(visited.count(str) == 0) {
                    visited.insert(str);
                    double cur = dfs(str, s, mp, visited, val * p.second);
                    if(cur != -1.0) return cur;
                }
            }
            
            return -1.0;
        }
    };
    

  • -2
    V

    Can someone please help me understand how this solution solves the query of type ab/bd @helloc93


  • 0

    @VRAMJI

    Both the input and queries in your question look vague. You may want to specify.

    This algorithm used in the top post is a typical backtracking search.


  • -2
    V

    @zzhai Okay, let me elaborate. Given, a/b = 3 and b/c = 4, solve for ab/bc. The answer should be 12.


  • 0

    @VRAMJI

    The problem is to evaluate division, so you intend to evaluate a/c?
    Say it's a/c. At first, 2 hashMaps populated in Solution.calcEquation()

    in hashMap pairs, it has (a, [b]), (b, [a, c]), (c, [b]).
    in hashMap valuePairs, it has (a, [3]), (b, [1/3, 4]), (c, [1/4]).

    in the backTrack procedure, it'll multiply 2 values to get the answer for a/c:
    a/c = a/b * b/c = valuePairs.get(a).get(0) * valuePairs.get(b).get(1) = 3 * 4 = 12.

    Hope I've answered your question.


  • 0

    Slightly modified the code in the top post, making it more "backTracky".

    public class Solution {
        Map<String, List<String>> pair; 
        Map<String, List<Double>> valuePair; 
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            int n = queries.length, m = equations.length;  
            if (n == 0) return new double[0];
            
            double[] res = new double[n]; 
            pair = new HashMap<>(); 
            valuePair = new HashMap<>(); 
            
            for (int i = 0; i < m; i++) {
                if (!pair.containsKey(equations[i][0])) {
                    pair.put(equations[i][0], new LinkedList<>());
                    valuePair.put(equations[i][0], new LinkedList<>()); 
                }
                if (!pair.containsKey(equations[i][1])) {
                    pair.put(equations[i][1], new LinkedList<>()); 
                    valuePair.put(equations[i][1], new LinkedList<>()); 
                }
                pair.get(equations[i][0]).add(equations[i][1]); 
                pair.get(equations[i][1]).add(equations[i][0]); 
                valuePair.get(equations[i][0]).add(values[i]); 
                valuePair.get(equations[i][1]).add(1 / values[i]); 
            }
            
            for (int i = 0; i < n; i++) {
                backTrack(queries[i][0], queries[i][1], new HashSet<String>(), 1.0, i, res); 
            }
            
            return res; 
        }
        
        public void backTrack(String start, String end, Set<String> set, double value, int pos, double[] res) {
            if (set.contains(start) || !pair.containsKey(start)) { res[pos] = -1.0; return; }  
            if (start.equals(end)) {res[pos] = value; return; }
            
            List<String> pairList = pair.get(start); 
            List<Double> valueList = valuePair.get(start); 
            
            set.add(start); 
            for (int i = 0; i < pairList.size(); i++) {
                backTrack(pairList.get(i), end, set, value * valueList.get(i), pos, res);   
                if (res[pos] != 0.0 && res[pos] != -1.0) return; // result already found. no need to keep searching. 
            }
            set.remove(start); 
        }
    }

  • -1
    V

    @zzhai No you haven't. I understand what you're saying. Your explanation works for queries of the form a/b. But there are test cases of the form ab/bc.

    Do you see my point? The numerator and the denominator are not single values. They are products themselves (ab)/(bc)


  • 0

    @VRAMJI said in Java AC Solution using graph:

    In this case, you not only evaluate division but also multiplication.
    I'd think this can't be part of the test set.


Log in to reply
 

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