題目

https://leetcode.com/problems/different-ways-to-add-parentheses/

題解

參考：C++ Solution [Faster than 100%] | Explained with diagrams

• The problem becomes easier when we think about these expressions as expression trees.
• We can traverse over the experssion and whenever we encounter an operator, we recursively divide the expression into left and right part and evaluate them seperately until we reach a situation where our expression is purely a number and in this case we can simply return that number.
• Since there can be multiple ways to evaluate an expression (depending on which operator you take first) we will get a list of reults from left and the right part.
• Now that we have all the possible results from the left and the right part, we can use them to find out all the possible results for the current operator.

import java.util.ArrayList; import java.util.List;class Solution {public boolean isOp(char c) {return c == '+' || c == '-' || c == '*' || c == '/';}public int cal(int a, char op, int b) {return switch (op) {case '+' -> a + b;case '-' -> a - b;case '*' -> a * b;default -> a / b;};}public List<Integer> diffWaysToCompute(String expression) {char[] exp = expression.toCharArray();List<Integer> list = new ArrayList<>();boolean numberOnly = true;for (int i = 0; i < exp.length; i++) {List<Integer> left = new ArrayList<>();List<Integer> right = new ArrayList<>();if (isOp(exp[i])) {numberOnly = false;left = diffWaysToCompute(expression.substring(0, i));right = diffWaysToCompute(expression.substring(i + 1, exp.length));}for (int j : left) {for (int k : right) {list.add(cal(j, exp[i], k));}}}if (numberOnly) list.add(Integer.valueOf(expression));return list;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 241. Different Ways to Add Parentheses | 241. 为运算表达式设计优先级（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。