一、題目

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.Example 1:Input: expression = "2-1-1"Output: [0,2]Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2Example 2:Input: expression = "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) = 10Constraints:1 <= expression.length <= 20expression consists of digits and the operator '+', '-', and '*'.All the integer values in the input expression are in the range [0, 99].

二、思路

• 首先題目叫求添加括號來計算結果，可以有重復值，需要將所有可以添加括號的可能遍歷
• 可以分解為子問題，遇到一個符號$+,?,?$那么計算左邊字符串可能的取值和右邊字符串可能的取值，然后合并得出當前字符串可能的取值
• 對于一個字符串需要遍歷所有的運算符號來獲得所有的情況
• 遞歸出口：當一個字符串沒有符號時即全部為數字，那么只有一種取值即字符串本身

三、代碼

class Solution { public:vector<int> diffWaysToCompute(string expression) {vector<int> ans;for (int i = 0; i < expression.size(); i++) {if (!(expression[i] >= '0' && expression[i] <= '9')) {//切割為左右vector<int> l = diffWaysToCompute(expression.substr(0, i));vector<int> r = diffWaysToCompute(expression.substr(i + 1, expression.size()));//將左右的結果保存在ansfor (int j = 0; j < l.size(); j++) {for (int k = 0; k < r.size(); k++) {switch(expression[i]) {case '+':ans.push_back(l[j] + r[k]);break;case '-':ans.push_back(l[j] - r[k]);break;case '*':ans.push_back(l[j] * r[k]);break;}}}}} if (ans.size() == 0) {//遞歸出口代表只有一個數字 這時候直接將數字進行轉化ans.push_back(stoi(expression));}return ans;} };

總結

以上是生活随笔為你收集整理的LeedCode 241. Different Ways to Add Parentheses的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。