leetcode Different Ways to Add Parentheses

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"

.

((2-1)-1) = 0
(2-(1-1)) = 2      

Output: 

[0, 2]

Example 2

Input: 

"2*3-4*5"

(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      

Output: 

[-34, -14, -10, -10, 10]

解題方法：

典型的分治算法，當遇到運算符時分為左右兩邊進行相同的運算。之後再在将左右兩邊的數值分别兩兩進行運算。

代碼詳情：

class Solution {

public:

    vector<int> diffWaysToCompute(string input) {

        vector<int> result;

        int size = input.size();

        for (int i = 0; i < size; i++) {

            char cur = input[i];

            if (cur == '+' || cur == '-' || cur == '*') {

                // Split input string into two parts and solve them recursively

                vector<int> result1 = diffWaysToCompute(input.substr(0, i));

                vector<int> result2 = diffWaysToCompute(input.substr(i+1));

                for (int p = 0; p < result1.size(); p++) {

                    for (int q = 0; q < result2.size(); q++) {

                        if (cur == '+')

                            result.push_back(result1[p]+result2[q]);

                        else if (cur == '-')

                            result.push_back(result1[p]-result2[q]);

                        else

                            result.push_back(result1[p]*result2[q]);    

                    }

                }

            }

        }

        // if the input string contains only number

        if (result.empty())

            result.push_back(atoi(input.c_str()));

        return result;

    }

};

複雜度分析：

設有n個num，計算x個num的時間為f(x)，則複雜度為[f(1)+f(n-1)+f(2)+f(n-2)+f(3)+f(n-3)+.....+f(n/2)+f(n/2)]*2 = f(n)