My java solution use Map and dfs with explanation


  • 0
    S

    Let's use default example:

    equations = [ ["a", "b"], ["b", "c"] ],
    values = [2.0, 3.0],
    queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
    

    [1] setup map (key is current string, value is a set)
    the set is contain an entry (key is relate string, value is relate value)

      for example : 
    
      equations[0][0] : "a" is current string , "b" is relate string, value is "a"/"b"=2.0;
      so, In the map: "a" --> Set { ("b" --> 1.0) };
    
      equations[0][1] : "b" is current string , "a" is relate string, value is "b"/"a"=0.5;
      so, In the map: "b" --> Set { ("a" --> 0.5) };
    
      equations[1][0] : "b" is current string , "c" is relate string, value is "b"/"c"=3.0;
      so, In the map: "b" --> Set { ("a" --> 0.5) , ("c" --> 3.0)};
    

    [2] setup mark (default is false)

    [3] use depth first search to search the graph

     when we visit one string, mark that string, which indicates this string will not visit again
    
     for example:
     
     res[0] = "a" -> ("b", 2.0) -> ("c", 3.0) = 2.0*3.0
    
    import java.util.*;
    import java.util.Map.Entry;
    public class Solution {
       double[] res;
       public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
          Map<String, Set<Entry<String, Double>>> map = new HashMap<>();
          Map<String, Boolean> mark = new HashMap<String, Boolean>();
    		
          for (int i = 0; i < equations.length; i++) {
             for (int j = 0; j < 2; j++) {
                Set<Entry<String, Double>> list = map.getOrDefault(equations[i][j], new HashSet<>());
                list.add(new AbstractMap.SimpleEntry<String, Double>(equations[i][~j&1], j==0? values[i] : 1/values[i]));
                map.put(equations[i][j], list);
                mark.put(equations[i][j], false);
             }
          }
    		
          res = new double[queries.length];
          for (int i = 0; i < queries.length; i++) {
             res[i] = -1.0;
             if (map.containsKey(queries[i][0]) && map.containsKey(queries[i][1])){
                helper(i, queries[i][0], queries[i][1], 1.0, map, mark);
                for (Entry<String, Boolean> e : mark.entrySet()) mark.put(e.getKey(), false);
             }
          }
          return res;
       }
    	
       private void helper(int i, String a, String b, double curValue, Map<String, Set<Entry<String, Double>>> map, Map<String, Boolean> mark) {
          if (a.equals(b)){res[i] = 1.0;return;}
          Set<Entry<String, Double>> set = map.get(a);
          mark.put(a, true);
          for (Entry<String, Double> entry : set) {
             if (!mark.get(entry.getKey()) && res[i] == -1){
                if (entry.getKey().equals(b)){
                   res[i] = curValue*entry.getValue();
                   return;
                }else {
                   helper(i, entry.getKey(), b, curValue*entry.getValue(), map, mark);
                }
             }
          }
       }
    }
    

Log in to reply
 

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