241 Different Ways to Add Parentheses 為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí)
Description:
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:
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
題目描述:
給定一個(gè)含有數(shù)字和運(yùn)算符的字符串，為表達(dá)式添加括號(hào)莹桅，改變其運(yùn)算優(yōu)先級(jí)以求出不同的結(jié)果暑椰。你需要給出所有可能的組合的結(jié)果。有效的運(yùn)算符號(hào)包含 +, - 以及 * 。
示例 :
示例 1:
輸入: "2-1-1"
輸出: [0, 2]
解釋:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
輸入: "2*3-4*5"
輸出: [-34, -14, -10, -10, 10]
解釋:
(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
思路:
- 分而治之
遞歸?回溯
比如 "2*3-4*5"可以劃分成 a: "2", "3-4*5"; b: "2*3", "4*5", c: "2*3-4", "5"
遞歸的終點(diǎn)是純數(shù)字, 要么是運(yùn)算結(jié)果, 要么是一個(gè)單個(gè)的數(shù)字
回溯是將分開(kāi)的兩個(gè)數(shù)字再得到運(yùn)算結(jié)果, 比如 b: "6" - "20" -> -14
時(shí)間復(fù)雜度O(Cn), 空間復(fù)雜度O(Cn), 其中 Cn為卡塔蘭數(shù) - 動(dòng)態(tài)規(guī)劃
dp[i][j]表示從第 i個(gè)數(shù)字到第 j個(gè)數(shù)字的所有情況
dp[i][i]表示一個(gè)數(shù)字, 就是 input中的數(shù)字
時(shí)間復(fù)雜度O(n ^ 3), 空間復(fù)雜度O(n ^ 3)
代碼:
C++:
class Solution
{
public:
vector<int> diffWaysToCompute(string input)
{
vector<int> nums, ops;
int num = 0;
for (int i = 0; i < input.size(); i++)
{
if (is_operator(input[i]))
{
nums.push_back(num);
ops.push_back(input[i]);
num = 0;
}
else num = num * 10 + input[i] - '0';
}
nums.push_back(num);
int n = nums.size();
vector<vector<vector<int>>> dp(n,vector<vector<int>>(n));
for (int i = 0; i < n; i++) dp[i][i].push_back(nums[i]);
for (int j = 1; j < n; j++) for (int i = j - 1; i >= 0; i--) for(int k = i; k < j; k++) for (int r1 : dp[i][k]) for(int r2 : dp[k + 1][j]) dp[i][j].push_back(calculate(r1, ops[k], r2));
return dp[0][n - 1];
}
private:
bool is_operator(const char& c)
{
return c == '+' or c == '-' or c == '*';
}
int calculate(const int& num1, const char& op, const int& num2)
{
return op == '+' ? num1 + num2 : (op == '-' ? num1 - num2 : num1 * num2);
}
};
Java:
class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> temp1 = diffWaysToCompute(input.substring(0, i)), temp2 = diffWaysToCompute(input.substring(i + 1));
for (int num1 : temp1) for (int num2 : temp2) {
if (c == '+') result.add(num1 + num2);
else if (c == '-') result.add(num1 - num2);
else if (c == '*') result.add(num1 * num2);
}
}
}
return result.isEmpty() ? new ArrayList<Integer>(){{ add(Integer.valueOf(input)); }} : result;
}
}
Python:
class Solution:
def diffWaysToCompute(self, input: str) -> List[int]:
return [int(input)] if input.isdigit() else [eval(f'{left}{c}{right}') for i, c in enumerate(input) for left in self.diffWaysToCompute(input[:i]) for right in self.diffWaysToCompute(input[i + 1:]) if c in '+-*']
