0241 solved.

liuyubobobo · liuyubobobo · commit 148e8279a813 · 2022-06-30T21:00:05.000-07:00
diff --git a/0001-0500/0241-Different-Ways-to-Add-Parentheses/cpp-0241/CMakeLists.txt b/0001-0500/0241-Different-Ways-to-Add-Parentheses/cpp-0241/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0241)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0241 main.cpp)
diff --git a/0001-0500/0241-Different-Ways-to-Add-Parentheses/cpp-0241/main.cpp b/0001-0500/0241-Different-Ways-to-Add-Parentheses/cpp-0241/main.cpp
@@ -0,0 +1,76 @@
+/// Source : https://leetcode.com/problems/different-ways-to-add-parentheses/
+/// Author : liuyubobobo
+/// Time   : 2022-06-30
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Brute Force
+/// Time Complexity: O(n!)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    vector<int> diffWaysToCompute(string exp) {
+
+        vector<int> nums;
+        vector<char> ops;
+        for(int start = 0, i = 1; i <= exp.size(); i ++)
+            if(i == exp.size() || !isdigit(exp[i])){
+                nums.push_back(atoi(exp.substr(start, i - start).c_str()));
+
+                if(i < exp.size()) ops.push_back(exp[i]);
+
+                start = i + 1;
+                i = start;
+            }
+
+//        for(int e: nums) cout << e << ' '; cout << '\n';
+//        for(char op: ops) cout << op << ' '; cout << '\n';
+
+        vector<int> res = dfs(nums, ops, 0, nums.size() - 1);
+        return res;
+    }
+
+private:
+    vector<int> dfs(const vector<int>& nums, const vector<char>& ops, int l, int r){
+
+        if(l == r) return {nums[l]};
+
+        vector<int> res;
+        for(int left_end = l; left_end < r; left_end ++){
+            vector<int> a = dfs(nums, ops, l, left_end);
+            vector<int> b = dfs(nums, ops, left_end + 1, r);
+
+            for(int e1: a)
+                for(int e2: b)
+                    res.push_back(calc(e1, e2, ops[left_end]));
+        }
+        return res;
+    }
+
+    int calc(int a, int b, char op){
+        if(op == '+') return a + b;
+        if(op == '-') return a - b;
+        if(op == '*') return a * b;
+
+        assert(false);
+        return -1;
+    }
+};
+
+
+void print_vec(const vector<int>& v){
+    for(int e: v) cout << e << ' '; cout << '\n';
+}
+
+int main() {
+
+    print_vec(Solution().diffWaysToCompute("2-1-1"));
+
+    print_vec(Solution().diffWaysToCompute("2*3-4*5"));
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -280,7 +280,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 238 | [Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) | [solution](https://leetcode.com/problems/product-of-array-except-self/solution/) | [C++](0001-0500/0238-Product-of-Array-Except-Self/cpp-0238/) | | [Python](0001-0500/0238-Product-of-Array-Except-Self/py-0238/) |
 | 239 | [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/description/) | [solution](https://leetcode.com/problems/sliding-window-maximum/solution/) | [C++](0001-0500/0239-Sliding-Window-Maximum/cpp-0239/) | | |
 | 240 | [Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/) | [solution](https://leetcode.com/problems/search-a-2d-matrix-ii/solution/) <br/> [缺：分治] | [C++](0001-0500/240-Search-a-2D-Matrix-II/cpp-240/) | | |
-| | | | | | |
+| 241 | [Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/) | [无] | [C++](0001-0500/241-Different-Ways-to-Add-Parentheses/cpp-241/) | | |
 | 242 | [Valid Anagram](https://leetcode.com/problems/valid-anagram/description/) | [solution](https://leetcode.com/problems/valid-anagram/solution/) | [C++](0001-0500/0242-Valid-Anagram/cpp-0242/) | | |
 | 243 | [Shortest Word Distance](https://leetcode.com/problems/shortest-word-distance/) | [solution](https://leetcode.com/problems/shortest-word-distance/solution/) | [C++](0001-0500/0243-Shortest-Word-Distance/cpp-0243/) | | |
 | 244 | [Shortest Word Distance II](https://leetcode.com/problems/shortest-word-distance-ii/) | [solution](https://leetcode.com/problems/shortest-word-distance-ii/solution/) | [C++](0001-0500/0244-Shortest-Word-Distance-II/cpp-0244/) | | |
