Esay understand Java solution, 3ms


  • 13
    Y
        public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
            double[] result = new double[query.length];
            // filter unexpected words
            // 过滤掉没有遇见过的字符
            Set<String> words = new HashSet<>();
            for (String[] strs : equations) {
                words.add(strs[0]);
                words.add(strs[1]);
            }
            for (int i = 0; i < query.length; ++i) {
                String[] keys = query[i];
                if (!words.contains(keys[0]) || !words.contains(keys[1])) result[i] = -1.0d;
                else {
                    Stack<Integer> stack = new Stack<>();
                    result[i] = helper(equations, values, keys, stack);
                }
            }
            return result;
        }
    
        public double helper(String[][] equations, double[] values, String[] keys, Stack<Integer> stack) {
            // 直接查找,key的顺序有正反
            // look up equations directly
            for (int i = 0; i < equations.length; ++i) {
                if (equations[i][0].equals(keys[0]) && equations[i][1].equals(keys[1])) return values[i];
                if (equations[i][0].equals(keys[1]) && equations[i][1].equals(keys[0])) return 1 / values[i];
            }
            // lookup equations by other equations
            // 间接查找,key的顺序也有正反
            for (int i = 0; i < equations.length; ++i) {
                if (!stack.contains(i) && keys[0].equals(equations[i][0])) {
                    stack.push(i);
                    double temp = values[i] * helper(equations, values, new String[]{equations[i][1], keys[1]}, stack);
                    if (temp > 0) return temp;
                    else stack.pop();
                }
                if (!stack.contains(i) && keys[0].equals(equations[i][1])) {
                    stack.push(i);
                    double temp = helper(equations, values, new String[]{equations[i][0], keys[1]}, stack) / values[i];
                    if (temp > 0) return temp;
                    else stack.pop();
                }
            }
            // 查不到,返回-1
            return -1.0d;
        }
    

    update:

    Thanks for @jason88628 remind me. change from stack to set will be better.

    update:

    Another way for this problem, but it need more memory and more time to build a whole map of equations.

    It's efficient when there is a large set of queries.

    public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
            // use table save string to integer
            Map<String, Integer> table = new HashMap<>();
            int len = 0;
            for (String[] strings : equations)
                for (String string : strings)
                    if (!table.containsKey(string)) table.put(string, len++);
    
            // init map by direct equation
            double[][] map = new double[len][len];
            for (int i = 0; i < len; ++i)
                for (int j = 0; j < len; ++j)
                    map[i][j] = (i == j ? 1.0d : -1.0d);
            for (int i = 0; i < equations.length; ++i) {
                String[] keys = equations[i];
                int row = table.get(keys[0]);
                int col = table.get(keys[1]);
                map[row][col] = values[i];
                map[col][row] = 1 / values[i];
            }
    
            // floyd-warshall like algorithm
            for (int i = 0; i < len; ++i) {
                for (int j = 0; j < len; ++j) {
                    for (int k = 0; k < len; ++k) {
                        if (map[j][i] >= 0d && map[i][k] >= 0d) map[j][k] = map[j][i] * map[i][k];
                    }
                }
            }
    
            // query now
            double[] result = new double[query.length];
            for (int i = 0; i < query.length; ++i) {
                String[] keys = query[i];
                Integer row = table.get(keys[0]);
                Integer col = table.get(keys[1]);
                if (row == null || col == null) result[i] = -1.0d;
                else result[i] = map[row][col];
            }
            return result;
        }
    

    update:
    A better way with union-find alogrithm. It takes less memory and time than the above one. But it's hard to understand.

    You can replace class Node with two arrays. In that way, it will be more efficient.

    public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
    
            // map string to integer
            Map<String, Integer> mIdTable = new HashMap<>();
            int len = 0;
            for (String[] words : equations)
                for (String word : words)
                    if (!mIdTable.containsKey(word)) mIdTable.put(word, len++);
    
            // init parent index and value
            Node[] nodes = new Node[len];
            for (int i = 0; i < len; ++i) nodes[i] = new Node(i);
    
            // union, you can take an example as follows
            // (a/b=3)->(c/d=6)->(b/d=12)
            for (int i = 0; i < equations.length; ++i) {
                String[] keys = equations[i];
                int k1 = mIdTable.get(keys[0]);
                int k2 = mIdTable.get(keys[1]);
                int groupHead1 = find(nodes, k1);
                int groupHead2 = find(nodes, k2);
                nodes[groupHead2].parent = groupHead1;
                nodes[groupHead2].value = nodes[k1].value * values[i] / nodes[k2].value;
            }
    
            // query now
            double[] result = new double[query.length];
            for (int i = 0; i < query.length; ++i) {
                Integer k1 = mIdTable.get(query[i][0]);
                Integer k2 = mIdTable.get(query[i][1]);
                if (k1 == null || k2 == null) result[i] = -1d;
                else {
                    int groupHead1 = find(nodes, k1);
                    int groupHead2 = find(nodes, k2);
                    if (groupHead1 != groupHead2) result[i] = -1d;
                    else result[i] = nodes[k2].value / nodes[k1].value;
                }
            }
            return result;
        }
    
        public int find(Node[] nodes, int k) {
            int p = k;
            while (nodes[p].parent != p) {
                p = nodes[p].parent;
                // compress
                nodes[k].value *= nodes[p].value;
            }
            // compress
            nodes[k].parent = p;
            return p;
        }
    
        private static class Node {
            int    parent;
            double value;
    
            public Node(int index) {
                this.parent = index;
                this.value = 1d;
            }
        }
    

  • 0
    J

    @yuxiaofei2016
    Is stack contains o(n)? How about change stack to set?


  • 0
    Y

    @jason88628 Yes, you are right.


  • 0
    R

    shouldn't we return -1.0 if any of the word is missing? (like a/e). So I think
    if (!words.contains(keys[0]) && !words.contains(keys[1])) should be
    if (!words.contains(keys[0]) || !words.contains(keys[1]))


  • 0
    Y

    @rhasan_82 Yes, my mistake. fix it


  • 0
    I

    @yuxiaofei2016 For each call of helper, you are going to iterate the whole equations? How could this be accepted, and 3ms? Need more TCs and more queries per setting!!!


  • 0
    Y
    This post is deleted!

  • 0
    Y

    @iambright Yes, my way is easy for understand. It's not efficient in the TestCase with large set of equations and queries.


  • 0
    Y
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    I

    Implementing the traditional Union-Find in a new way is very impressive.


Log in to reply
 

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