4ms clean solution, no graph


  • 0
    I
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            final Map<String, List<Element>> map = new HashMap<>();
            
            for(int i=0; i<equations.length; i++) {
                final String a = equations[i][0];
                final String b = equations[i][1];
                final double v = values[i];
                if(a.equals(b)) continue;
                
                if(!map.containsKey(a)) map.put(a, new LinkedList<>());
                if(!map.containsKey(b)) map.put(b, new LinkedList<>());
                
                map.get(a).add(new Element(a, b, v));
                map.get(b).add(new Element(b, a, 1/v));
            }
            
            final double[] ans = new double[queries.length];
            
            for(int i=0; i<queries.length; i++) {
                final String a = queries[i][0];
                final String b = queries[i][1];
    
                if(!map.containsKey(a) || !map.containsKey(b)) {
                    ans[i] = -1;
                    continue;
                }
                
                if(a.equals(b)) {
                    ans[i] = 1;
                    continue;
                }
    
                ans[i] = search(map, a, b, new HashSet<>());
            }
            
            return ans;
        }
        
        private double search(final Map<String, List<Element>> map, final String a, final String b, final Set<String> used) {
            if(!map.containsKey(a)) return -1;
            
            used.add(a);
            
            final List<Element> list = map.get(a);
            
            for(Element element : list) {
                if(element.b.equals(b)) {
                    return element.v;
                }else if(!used.contains(element.b)){
                    final double ans = search(map, element.b, b, used);
                    if(ans != -1) {
                        return element.v * ans;
                    }
                }
            }
            
            return -1;
        }
        
        private class Element {
            final String a;
            final String b;
            final double v;
            Element(final String a, final String b, final double v) {
                this.a = a;
                this.b = b;
                this.v = v;
            }
        }
        
        
    }
    

Log in to reply
 

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