Leetcode hard level: 1320. Minimum Distance to Type a Word Using Two Fingers

April 1, 2022 

1320. Minimum Distance to Type a Word Using Two Fingers

Here is the link. 

March 31, 2022
Introduction
There are so many things to learn from this hard level practice. What I did is to find a C# solution, and then try to run a simple test case, and see if I can understand the algorithm from this simple test case.

TLE error | 54/54 TLE error
I need to figure out how it is designed, and also there is TLE error to run against Leetcode online judge.

The following C# code passes online judge.

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

namespace _1320_minimum_distance
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            var result = test.MinimumDistance("CAKE");
        }
        
        /// <summary>
        /// study code:
        /// https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/478092/C-Solution-Top-down-DP-with-Memoization
        /// </summary>
        /// <param name="word"></param>
        /// <returns></returns>
        public int MinimumDistance(string word)
        {
            int sum = 0;
            var result = int.MaxValue;
            var n = word.Length;
            
            var memo = new int[n, n];

            // How to analyze the following statements?
            // 
            for (int i = 0; i < n - 1; i++)
            {
                result = Math.Min(result, sum + calMinimumDistance(word, i, i + 1, memo));
                sum += calDistance(word[i], word[i + 1]);
            }

            return result;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="word"></param>
        /// <param name="leftFinger"></param>
        /// <param name="rightFinger"></param>
        /// <param name="memo"></param>
        /// <returns></returns>
        private int calMinimumDistance(string word, int leftFinger, int rightFinger, int[,] memo)
        {
            int next = 1 + Math.Max(leftFinger, rightFinger);
            if (next == word.Length)
            {
                return 0;
            }

            if (memo[leftFinger, rightFinger] != 0)
            {
                return memo[leftFinger, rightFinger];
            }

            // think about two cases:
            // either left finger moves or right finger moves to word[next]
            // left finger - 
            // right finger -
            memo[leftFinger, rightFinger] = 
                Math.Min(calMinimumDistance(word, leftFinger, next, memo) + calDistance(word[rightFinger], word[next]),
                         calMinimumDistance(word, next, rightFinger, memo) + calDistance(word[leftFinger], word[next]));

            return memo[leftFinger, rightFinger];
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="ch1"></param>
        /// <param name="ch2"></param>
        /// <returns></returns>
        private int calDistance(int ch1, int ch2)
        {
            int a = ch1 - 'A';
            var b = ch2 - 'A';
            // row distance + column distance
            return Math.Abs(a / 6 - b / 6) + Math.Abs(a % 6 - b % 6);
        }
    }
}