Java 2 ms solution with comments, beats 97.96%, using value matrix and DFS


  • 2
    B
    import java.util.*; 
    
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            
            // Use result to store the answers to the queries
            double[] result = new double[queries.length];
            int result_index = 0;
            
            // Use hashtable to find the index of a string to the value matrix
            Hashtable<String, Integer> hashtable = new Hashtable<>();
            
            // Calculate indexes for strings
            int index = 0;
            for (String[] temp: equations) {
                if (!hashtable.containsKey(temp[0])) {
                    hashtable.put(temp[0], index++);
                }
                if (!hashtable.containsKey(temp[1])) {
                    hashtable.put(temp[1], index++);
                }
            }
            
            // Initialize value_matrix
            double[][] value_matrix = new double[index + 1][index + 1];
            for (int i = 0; i < index + 1; ++i) {
                for (int j = 0; j < index + 1; ++j) {
                    if (i == j) {
                        value_matrix[i][j] = 1.0;
                    }
                    else {
                        value_matrix[i][j] = -1.0;
                    }
                }
            }
            
            // Store values in value_matrix
            for (int i = 0; i < equations.length; ++i) {
                int index_1 = hashtable.get(equations[i][0]);
                int index_2 = hashtable.get(equations[i][1]);
                value_matrix[index_1][index_2] = values[i];
                value_matrix[index_2][index_1] = 1 / values[i];
            }
            
            
            for (String[] query: queries) {
                
                // Cannot find such input string in hashtable 
                if (!(hashtable.containsKey(query[0]) && hashtable.containsKey(query[1]))) {
                    result[result_index++] = -1.0;
                }
                else {
                    
                    // Calculate indexes for the query
                    int index_1 = hashtable.get(query[0]);
                    int index_2 = hashtable.get(query[1]);
                    
                    // The value exists
                    if (value_matrix[index_1][index_2] > 0.0) {
                        result[result_index++] = value_matrix[index_1][index_2];
                    }
                    
                    // The value is -1.0, need calculation using DFS
                    else {
                        Set visited = new HashSet<Integer>();
                        visited.add(index_1);
                        result[result_index++] = find(visited, value_matrix, index_1, index_2);
                    }
                }
            }
            
            return result;
             
        }
        
        // Find the value of 'now'/'target', if can not find, return -1.0
        public double find(Set visited, double[][] value_matrix, int now, int target) {
            
            // Value found
            if (value_matrix[now][target] > 0.0) return value_matrix[now][target];
            
            // For unvisited neighbors of 'now', keep searching using DFS
            for (int i = 0; i < value_matrix.length; ++i) {
                if (!visited.contains(i) && value_matrix[now][i] > 0.0) {
                    visited.add(i);
                    double temp = find(visited, value_matrix, i, target);
                    visited.remove(i);
                    if (temp > 0.0) {
                        // Update the value_matrix
                        value_matrix[now][target] = value_matrix[now][i] * temp;
                        return value_matrix[now][target];
                    }
                }
            }
            return -1.0;
        }
    }
    

Log in to reply
 

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