Simple java 4ms solution with graph


  • 0

    Build a graph, then use BFS or DFS.

    public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
            HashMap<String, Integer> map=new HashMap();
            int count=0;
            for(String[] i:equations)
            {
                if(!map.containsKey(i[0]))
                    map.put(i[0],count++);
                if(!map.containsKey(i[1]))
                    map.put(i[1],count++);
            }
            double[][] graph=new double[count][count];
            Queue<int[]> queue=new LinkedList();
            for(int i=0;i<values.length;i++)
            {
                int x=map.get(equations[i][0]),y=map.get(equations[i][1]);
                graph[x][y]=values[i];
                graph[y][x]=1/values[i];
                graph[x][x]=1;
                graph[y][y]=1;
                queue.offer(new int[]{x,y});
                queue.offer(new int[]{y,x});
            }
            while(!queue.isEmpty())
            {
                int[] element=queue.poll();
                for(int i=0;i<count;i++)
                {
                    if(i==element[0]||graph[element[1]][i]==0||graph[element[0]][i]!=0)
                        continue;
                    graph[element[0]][i]=graph[element[0]][element[1]]*graph[element[1]][i];
                    graph[i][element[0]]=1/graph[element[0]][i];
                    queue.offer(new int[]{element[0],i});
                    queue.offer(new int[]{i,element[0]});
                }
            }
            double[] result=new double[query.length];
            for(int i=0;i<query.length;i++)
            {
                if(map.containsKey(query[i][0])&&map.containsKey(query[i][1]))
                    result[i]=graph[map.get(query[i][0])][map.get(query[i][1])];
                if(result[i]==0)
                    result[i]=-1;
            }
            return result;
        }
    

Log in to reply
 

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