399. 除法求值 (opens new window)

1.dfs+回溯

分析：深搜消除匹配。注意匹配过程中可能会出现循环依赖的情况，因此需要使用标志位列表，标记使用过的字符串，防止搜索时无限循环。退出当前搜索之后需要对使用位进行回溯。

搜索时当分子分母相同时，可能存在如下情况：

• 经过多次匹配消元得到的最终结果
• 搜索前可以直接消元，属于在等式中出现过的字符串，此时结果为1
• 搜索前可以直接消元，属于在等式中未出现过的字符串，置为-1

剪枝：如果某个分支已经成功消元，那么需要一个判断位success回传给父节点，直接退出搜索。否则得到的结果，会在“判断无法消元”的分支中重写为-1覆盖。

class Solution {
    double[] res;
    boolean success;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        List<String> used = new ArrayList<>();
        res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            success = false;
            List<String> list = queries.get(i);
            dfs(equations, values, used, list.get(0), list.get(1), 1, i);
        }
        return res;
    }

    public void dfs(List<List<String>> equations, double[] values, List<String> used, String source, String des, double mul, int index) {
        if (source.equals(des)) {
            if (used.size() > 0)
                res[index] = mul;
            else {
                boolean check = false;
                for (int i = 0; i < equations.size(); i++) {
                    List<String> list = equations.get(i);
                    if (list.get(0).equals(source) || list.get(1).equals(source)) {
                        check = true;
                    }
                }
                if (!check) res[index] = (double) -1.0;
                else res[index] = (double) 1.0;
            }
            success = true;
            return;
        }
        boolean check = false;
        for (int i = 0; i < equations.size(); i++) {
            if (success) return;
            List<String> list = equations.get(i);
            if (list.get(0).equals(source) && !used.contains(list.get(1))) {
                check = true;
                used.add(list.get(0));
                dfs(equations, values, used, list.get(1), des, mul * values[i], index);
                used.remove(used.size() - 1);
                if (list.get(1).equals(des)) break;

            }
            if (list.get(1).equals(source) && !used.contains(list.get(0))) {

                check = true;
                used.add(list.get(1));
                dfs(equations, values, used, list.get(0), des, mul / values[i], index);
                used.remove(used.size() - 1);
                if (list.get(0).equals(des)) break;
            }
        }
        if (!check) res[index] = (double) -1.0;
    }
}