Very Easy Java Solution. Use 2D Array.


  • 1
    L

    The idea is very simple. Just convert string to index numbers. Then fill the matrix with known values. When each query comes, dfs to find if there is a result. Fill the entry to reduce redundant if the result is valid.

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            //Mapping string to index
            int index = 0;
            Map<String, Integer> mapping = new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                if (!mapping.containsKey(equations[i][0])) mapping.put(equations[i][0], index++);
                if (!mapping.containsKey(equations[i][1])) mapping.put(equations[i][1], index++);
            }
            
            //Fill matrix with known values
            int n = mapping.size();
            double[][] matrix = new double[n][n];
            for (int i = 0; i < values.length; i++) {
                int row = mapping.get(equations[i][0]);
                int col = mapping.get(equations[i][1]);
                matrix[row][col] = values[i];
                matrix[col][row] = 1.0 / values[i];
                matrix[row][row] = 1.0;
            }
            
            //DFS to get values
            double[] res = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                if (!mapping.containsKey(queries[i][0]) || !mapping.containsKey(queries[i][1])) {
                    res[i] = -1.0;
                } else {
                    int row = mapping.get(queries[i][0]);
                    int col = mapping.get(queries[i][1]);
                    res[i] = dfs(matrix, row, col, new HashSet<>());
                }
            }
            
            return res;
        }
        
        //DFS to get result, use set to record which variables are used
        private double dfs(double[][] matrix, int row, int col, Set<Integer> visited) {
            if (matrix[row][col] != 0.0) {
                return matrix[row][col];
            }
            
            for (int i = 0; i < matrix.length; i++) {
                if (i == row || visited.contains(i)) continue;
                if (matrix[i][col] != 0.0) {
                    double factor = matrix[i][col];
                    visited.add(i);
                    double tmp = dfs(matrix, row, i, visited);
                    visited.remove(i);
                    if (tmp != -1.0) {
                        matrix[row][col] = tmp * factor;
                        return matrix[row][col];
                    }
                }
            }
            
            return -1.0;
        }
    }
    

Log in to reply
 

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