241. 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: "23-45"
Output: [-34, -14, -10, -10, 10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10


我的答案:先把数字和符号存到两个vector里面,然后要recursion,recursion有重复所以用dp,这里这个dp是3重vector,空间复杂度可能是O(n^2 * ans_size), ans_size可能是O(n^2) (算不清楚了,晕),总之空间复杂度很高,写的时候特别怕。结果出人意料的好。

class Solution {
private:
    vector<vector<vector<int>>> val_dp;
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> nums;
        vector<char> symbols{'+'};
        
        int len = input.size();
        int num = 0;
        for (int i=0; i<len; ++i) {
            char c = input[i];
            if (isdigit(c))
                num = num*10 + (c-'0');
            else {
                nums.push_back(num);
                symbols.push_back(c);
                num = 0;
            }
        }
        nums.push_back(num);
        
        len = nums.size();
        val_dp = vector<vector<vector<int>>>(len, vector<vector<int>>(len, vector<int>()));
        vector<int> ans = dp(0, len, nums, symbols);

        return ans;
    }
    
    vector<int> dp(int start, int end, const vector<int>& nums, const vector<char>& symbols) {
        if (start == end)
            return {};
        if (start+1 == end)
            return {nums[start]};
        if (val_dp[start][end-1].size() > 0)
            return val_dp[start][end-1];
        
        vector<int> ret, left, right;
        for (int i=start+1; i<end; ++i) {
            if (val_dp[start][i-1].size() == 0) {
                left = dp(start, i, nums, symbols);
                val_dp[start][i-1] = left;
            }
            else
                left = val_dp[start][i-1];
            
            if (val_dp[i][end-1].size() == 0) {
                right = dp(i, end, nums, symbols);
                val_dp[i][end-1] = right;
            }
            else
                right = val_dp[i][end-1];
            
            // cout << left.size() << " - " << right.size() << endl;
            for (const auto& l : left) {
                for (const auto& r : right) {
                    if (symbols[i] == '+')
                        ret.push_back(l+r);
                    else if (symbols[i] == '-')
                        ret.push_back(l-r);
                    else
                        ret.push_back(l*r);
                }
            }
        }
        val_dp[start][end-1] = ret;
        return ret;
    }
};

Runtime: 4 ms, faster than 80.93% of C++ online submissions for Different Ways to Add Parentheses.
Memory Usage: 7.4 MB, less than 88.38% of C++ online submissions for Different Ways to Add Parentheses.

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容