241. Different Ways to Add Parentheses

Here is my discussion post.

It is a medium level algorithm. I came cross the algorithm since I read the article about one Google onsite in 2019. This algorithm is one of interview algorithms.

Here are the highlights of my practice in May 2019:

1. Base case, make it clear and also the position is at the very beginning - input is an integer; otherwise the whole list is empty.
2. Brute force solution, the idea is any operator in the expression can be the last one to be calculated. In other words, expression is constructed as "part1 + operator + part2" whereas part1 and part2 are the subproblems.
3. Apply memoization to avoid redundant calculation - if there is time.
4. Extra note on step 2, work on test case "1+2", and make sure that part1 and part2 are correct. Detail see comment

Time complexity

It is expontial time complexity since any of operators can be the last one, so the total options will be N!, N is total operators.

It is also very interesting to review my practices in 2015 and 2016. I have to push myself to practice more solutions on this problem in 2019.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _241_different_way_to_add_parenthesis
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase1(); 
        }

        public static void RunTestcase1()
        {
            var result = DiffWaysToCompute("2-1-1"); 
        }

        public static Dictionary<string, IList<int>> map = new Dictionary<string, IList<int>>();

        /// <summary>
        /// May 27, 2019
        /// study code 
        /// https://leetcode.com/problems/different-ways-to-add-parentheses/discuss/66328/A-recursive-Java-solution-(284-ms)/179202
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static IList<int> DiffWaysToCompute(string input)
        {
            if (map.ContainsKey(input))
            {
                return map[input]; 
            }

            var results = new List<int>();

            // base case - input is an integer
            if (!(input.Contains("+") || input.Contains("-") || input.Contains("*")))
            {
                results.Add(Convert.ToInt32(input)); 
            }

            // brute force solution - go over each operator in the expression
            for (int i = 0; i < input.Length; i++)
            {
                var current = input[i];
                var isOperator = "+-*".IndexOf(current) != -1;
                if (!isOperator)
                    continue; 

                /*
                 * 1 + 2
                 * part1 "1"
                 * part2 "2"
                 * '+' will not be counted by part1 or part2
                 */
                var part1 = input.Substring(0, i);
                var part2 = input.Substring(i + 1);  // bug fix, i + 1 instead of i

                var list1 = DiffWaysToCompute(part1);
                var list2 = DiffWaysToCompute(part2);

                foreach (var item1 in list1)
                {
                    foreach (var item2 in list2)
                    {
                        int calculated = 0;
                        if (current == '+')
                        {
                            calculated = item1 + item2;
                        }
                        else if (current == '-')
                        {
                            calculated = item1 - item2; 
                        }
                        else if (current == '*')
                        {
                            calculated = item1 * item2;
                        }

                        results.Add(calculated); 
                    }
                }                
            }

            map.Add(input, results); 

            return results;
        }
    }
}

Actionable Items

I am so glad to review my practice in 2015 and 2018. I can tell some difference based on the practice compared to a few years ago.