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);
}
}
}
