leetcode Question: 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]

Analysis:

The essential usage of parentheses in this problem is the order of computation. In this problem, we are asked to find every possible groups of operations in the formula.

First, let's see how to make groups in the formula. The operators is the natural way of dividing the string into groups: left part and right part. Also, the adding parentheses procedure can be converted into a more straightforward procedure: group string according different operators. For example:

String: "2-1-1"
adding () in 2-(1-1) is same to group string "2-1-1" using the 1st '-' operator: '2', '-' , '1-1'. We may also say, the left part of '-' is '2', the right part of '-' is '1-1'. So, for this grouping, the final value is "left part" - "right part".


But what if we have a long string with multiple operators? Usually recursion is a good way handling the case.  Let's see the string "2*3-4*5"

We have group:
2,    *,    3-4*5

For  the right part 3-4*5, we further take the grouping :
3,    - ,    4*5   = -17  and 3-4,    *,    5. = -5

The group  2,  *,   3-4*5,  now becomes:
2,  *,   [-17,  -5], which means, there are multiple possible values in the right part of this group. Next, just compute all the combinations of this group will give us the result:  -34 and -10.

Code(C++):

class Solution {
public:
    vector<int> search(string input){
        vector<int> res;
        vector<int> left;
        vector<int> right;
        
        if (input.find('+')==-1 &&input.find('-')==-1 && input.find('*')==-1){
            int tmp;
            stringstream(input) >> tmp;
            res.push_back(tmp);
        }else{
            for (int i=1; i<input.size(); i++){
                if (input[i] == '+' || input[i] == '-' ||input[i] == '*'){
                    left = search(input.substr(0,i));
                    right = search(input.substr(i+1));
                    for (int j=0;j<left.size();j++){
                        for (int k=0;k<right.size();k++){
                            int val = 0;
                            if (input[i] == '+') {val = left[j]+right[k];}
                            if (input[i] == '-') {val = left[j]-right[k];}
                            if (input[i] == '*') {val = left[j]*right[k];}
                            res.push_back(val);
                        }
                    }
                }
            }
        }
        return res;
    }

    vector<int> diffWaysToCompute(string input) {
        vector<int> result;
        if (input.size() == 0){ return result; }
        return search(input);
        
    }
};

Code(Python):

class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        res = []
        right = []
        left = []
        if len(input) == 0:
            return res
        if input.find('+') == -1 and input.find('-') == -1 and input.find('*') == -1:
            res.append(int(input))
        else:
            count = 0
            for ch in input:
                if ch in ['+', '-', '*']:
                    left = self.diffWaysToCompute(input[0:count])
                    right = self.diffWaysToCompute(input[count+1::])
                    for l in left:
                        for r in right:
                            val = 0
                            if ch == '+':
                                val = l + r
                            if ch == '-':
                                val = l - r
                            if ch == '*':
                                val = l * r
                            res.append(val)
                count+=1
        return res
        
                            
                
        

leetcode Question 23: Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis:

Because the requirement "height balanced", this problem becomes relative easy.
Just recursively use the middle element in the array as the root node of the current tree(sub tree).

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode* cbst(vector<int> &num, int st, int ed){
        if (st>ed){
            return NULL;
        }else{
            int mid = st+(ed-st)/2;
            TreeNode *bst=new TreeNode(num[mid]);
            bst->left = cbst(num,st,mid-1);
            bst->right = cbst(num,mid+1,ed);
            return bst;
        }
    }

    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (num.size()==0){return NULL;}
        return cbst(num,0,num.size()-1);
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param num, a list of integers
    # @return a tree node
    def bst(self, num, st, ed):
        if st > ed:
            return None
        mid = st + (ed - st)/2
        left = self.bst(num, st, mid - 1)
        root = TreeNode(num[mid])
        right = self.bst(num, mid + 1, ed)
        root.left = left
        root.right = right
        return root
    
    def sortedArrayToBST(self, num):
        n = len(num)
        if n == 0:
            return None
        return self.bst(num, 0, n-1)