CODEWITHSUNDEEP
c#dynamic-programmingmemoization
Suresh Iyengar
Suresh Iyengar

Reputation: 59

Aibohphobia SPOJ

I am trying to solve this exercise.

I have a solution, as below, but I am getting Time Limit Exceeded error. I want to learn why this code is inefficient since I am doing memoization. 

namespace Aibohphobia
{
    class Test
    {
        static Dictionary<string, int> memo = new Dictionary<string, int>();
        static int Main(string[] args)
        {
            string num = Console.ReadLine();
            int N = int.Parse(num);
            string input = string.Empty;
            for (int i = 0; i < N; i++)
            {
                memo = new Dictionary<string, int>();
                input = Console.ReadLine();
                int count = new Test().insert(input, 0, input.Length - 1);
                Console.WriteLine(count);
            }
            return 0;
        }

        int insert(string input, int start, int end)
        {
            int count = 0;
            var key = start + "_" + end;

            if (start >= end)
                return 0;            
            if (memo.ContainsKey(key))
                return memo[key];
            if (input[start] == input[end])
            {
                count += insert(input, start + 1, end - 1);
            }
            else
            {
                int countLeft = 1 + insert(input, start + 1, end);
                int countRight = 1 + insert(input, start, end - 1);
                count += Math.Min(countLeft, countRight);
            }

            memo.Add(key, count);
            return count;
        }    
  }
}

Upvotes: 3

Views: 90

Answers (1)

marcelovca90
marcelovca90

Reputation: 2804

You are memoizing your results in a Dictionary<string, int>, which is, essentially, a hash table. It means that every time you want to retrieve a value for a given key, you must calculate the hash function of the key.

In this case, since the type of your key is string, the evaluation of the hash function is surely slowing your execution. I suggest that you memoize your values for the DP in int[][] matrix, therefore you can retrieve the values you want much faster.

In order to achieve that, you will have figure out how to map your strings to ints. You can find a brief tutorial on how to do that here: String Hashing for competitive programming, where the author explains simple string hashing techniques.

Upvotes: 1

Related Questions