LeetCode: 241. Different Ways to Add Parentheses

题目描述

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: "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

解题思路 —— 暴力搜索

这是一道排列组合问题，每个运算符号都可以将表达式分为两半，分别计算每一半，然后再计算运算符。

AC 代码

class Solution {
private:
    int cal(char op, int lhv, int rhv)
    {
        if(op == '+')
        {
            return lhv+rhv;
        }
        else if(op == '-')
        {
            return lhv-rhv;
        }
        else
        {
            return lhv*rhv;
        }
    }
    // [beg, end)
    vector<int> diffWaysToCompute(const vector<int>& nums, const string& opers, int beg, int end)
    {
        if(beg >= end) return {};
        else if(beg + 1 == end) return {nums[beg]};
        
        vector<int> res;
        for(size_t i = beg+1; i < end; ++i)
        {
            vector<int> leftRes = diffWaysToCompute(nums, opers, beg, i);
            vector<int> rightRes = diffWaysToCompute(nums, opers, i, end);

            for(int li = 0; li < leftRes.size(); ++li)
            {
                for(int ri = 0; ri < rightRes.size(); ++ri)
                {
                    res.push_back(cal(opers[i-1], leftRes[li], rightRes[ri]));
                }
            }
        }
        return res;
    }
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> nums;
        string opers;
        int curNum = 0;
        
        for(size_t i = 0; i < input.size(); ++i)
        {
            if(input[i] >= '0' && input[i] <= '9')
            {
                curNum = curNum*10+input[i]-'0';
            }
            else
            {
                nums.push_back(curNum);
                curNum = 0;
                opers.push_back(input[i]);
            }
            
            if(i == input.size()-1)
            {
                nums.push_back(curNum);
                curNum = 0;
            }
        }
        
        return diffWaysToCompute(nums, opers, 0, nums.size());
    }
};