Different Ways to Add Parentheses (M)

題目

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

題意

給定一串數字運算式，可以任意添加括號，求所有可能得到的結果，

思路

難點在于如何添加括號來得到不同的運算式，可以這樣考慮，每一個算術運算式都可以拆分成三個部分，左運算元、運算子、右運算元，即 \((...)\ ?\ (...)\) 的形式，只要改變每個括號內運算元的個數，得到的一定是不一樣的括號形式；而每一個括號里又是一個算數運算式，可以遞回的進行處理，最終就能得到所有括號的組合形式，

代碼實作

Java

分治法

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        if (input.isEmpty()) {
            return new ArrayList<>();
        }

      	// 先將字串拆分成運算元集合和運算子集合，便于處理
        List<Character> ops = new ArrayList<>();
        List<Integer> nums = new ArrayList<>();
        int num = 0;
        for (char c : input.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + c - '0';
            } else {
                ops.add(c);
                nums.add(num);
                num = 0;
            }
        }
        nums.add(num);

        return diff(nums, ops, 0, nums.size() - 1);
    }

    private List<Integer> diff(List<Integer> nums, List<Character> ops, int left, int right) {
        List<Integer> list = new ArrayList<>();

        if (left == right) {
            list.add(nums.get(left));
            return list;
        }

        for (int mid = left; mid < right; mid++) {
            List<Integer> part1 = diff(nums, ops, left, mid);
            List<Integer> part2 = diff(nums, ops, mid + 1, right);
            for (int i = 0; i < part1.size(); i++) {
                for (int j = 0; j < part2.size(); j++) {
                    int num1 = part1.get(i), num2 = part2.get(j);
                    char op = ops.get(mid);
                    list.add(op == '-' ? num1 - num2 : op == '+' ? num1 + num2 : num1 * num2);
                }
            }
        }

        return list;
    }
}

記憶化優化

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        return diffWaysToCompute(input, new HashMap<>());
    }

    private List<Integer> diffWaysToCompute(String input, Map<String, List<Integer>> record) {
        List<Integer> list = new ArrayList<>();

        if (input.isEmpty())
            return list;
        if (record.containsKey(input))
            return record.get(input);

        for (int i = 0; i < input.length(); i++) {
          	// 根據運算子劃分左右
            if (!Character.isDigit(input.charAt(i))) {
                char op = input.charAt(i);
                List<Integer> left = diffWaysToCompute(input.substring(0, i), record);
                List<Integer> right = diffWaysToCompute(input.substring(i + 1), record);
                for (int p = 0; p < left.size(); p++) {
                    for (int q = 0; q < right.size(); q++) {
                        int num1 = left.get(p), num2 = right.get(q);
                        list.add(op == '-' ? num1 - num2 : op == '+' ? num1 + num2 : num1 * num2);
                    }
                }
            }
        }

        // list為空，說明不存在運算子，input為完整數字
        if (list.size() == 0) {
            list.add(Integer.parseInt(input));
        }
        
        record.put(input, list);
        return list;
    }
}

標籤：其他

上一篇：0014. Longest Common Prefix (E)

下一篇：十大排序演算法