1320. Minimum Distance to Type a Word Using Two Fingers

/**
 * Problem: LeetCode 1320 - Minimum Distance to Type a Word Using Two Fingers
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;

class Solution {
    public int minimumDistance(String word) {
        int[] dp = new int[27];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[26] = 0;

        for (int i = 1; i < word.length(); i++) {
            int curr = word.charAt(i) - 'A';
            int prev = word.charAt(i - 1) - 'A';
            int[] nextDp = new int[27];
            Arrays.fill(nextDp, Integer.MAX_VALUE);

            for (int j = 0; j < 27; j++) {
                if (dp[j] == Integer.MAX_VALUE) continue;

                // Case 1: finger at prev moves to curr, other finger remains at j
                int cost1 = dp[j] + dist(prev, curr);
                nextDp[j] = Math.min(nextDp[j], cost1);

                // Case 2: finger at j moves to curr, finger at prev becomes other finger
                int cost2 = dp[j] + dist(j, curr);
                nextDp[prev] = Math.min(nextDp[prev], cost2);
            }

            dp = nextDp;
        }

        int minCost = Integer.MAX_VALUE;
        for (int cost : dp) {
            minCost = Math.min(minCost, cost);
        }
        return minCost;
    }

    private int dist(int a, int b) {
        if (a == 26 || b == 26) return 0;
        int r1 = a / 6, c1 = a % 6;
        int r2 = b / 6, c2 = b % 6;
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }
}

"""
Problem: LeetCode 1320 - Minimum Distance to Type a Word Using Two Fingers
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
class Solution:
    def minimumDistance(self, word: str) -> int:
        def dist(a: int, b: int) -> int:
            if a == 26 or b == 26:
                return 0
            return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)

        dp = [float('inf')] * 27
        dp[26] = 0

        for i in range(1, len(word)):
            curr = ord(word[i]) - ord('A')
            prev = ord(word[i - 1]) - ord('A')
            next_dp = [float('inf')] * 27

            for j in range(27):
                if dp[j] == float('inf'):
                    continue
                cost1 = dp[j] + dist(prev, curr)
                if cost1 < next_dp[j]:
                    next_dp[j] = cost1

                cost2 = dp[j] + dist(j, curr)
                if cost2 < next_dp[prev]:
                    next_dp[prev] = cost2

            dp = next_dp

        return min(dp)

/**
 * Problem: LeetCode 1320 - Minimum Distance to Type a Word Using Two Fingers
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
private:
    int dist(int a, int b) {
        if (a == 26 || b == 26) return 0;
        int r1 = a / 6, c1 = a % 6;
        int r2 = b / 6, c2 = b % 6;
        return abs(r1 - r2) + abs(c1 - c2);
    }

public:
    int minimumDistance(string word) {
        vector<int> dp(27, INT_MAX);
        dp[26] = 0;

        for (int i = 1; i < (int)word.size(); ++i) {
            int curr = word[i] - 'A';
            int prev = word[i - 1] - 'A';
            vector<int> nextDp(27, INT_MAX);

            for (int j = 0; j < 27; ++j) {
                if (dp[j] == INT_MAX) continue;

                cost1_update: {
                    int cost1 = dp[j] + dist(prev, curr);
                    nextDp[j] = min(nextDp[j], cost1);
                }

                cost2_update: {
                    int cost2 = dp[j] + dist(j, curr);
                    nextDp[prev] = min(nextDp[prev], cost2);
                }
            }

            dp = move(nextDp);
        }

        int minCost = INT_MAX;
        for (int cost : dp) {
            minCost = min(minCost, cost);
        }
        return minCost;
    }
};

/**
 * Problem: LeetCode 1320 - Minimum Distance to Type a Word Using Two Fingers
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {string} word
 * @return {number}
 */
var minimumDistance = function(word) {
    const dist = (a, b) => {
        if (a === 26 || b === 26) return 0;
        const r1 = Math.floor(a / 6), c1 = a % 6;
        const r2 = Math.floor(b / 6), c2 = b % 6;
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    };

    let dp = new Array(27).fill(Infinity);
    dp[26] = 0;

    for (let i = 1; i < word.length; i++) {
        const curr = word.charCodeAt(i) - 65;
        const prev = word.charCodeAt(i - 1) - 65;
        const nextDp = new Array(27).fill(Infinity);

        for (let j = 0; j < 27; j++) {
            if (dp[j] === Infinity) continue;

            // Case 1: finger at prev moves to curr
            const cost1 = dp[j] + dist(prev, curr);
            if (cost1 < nextDp[j]) nextDp[j] = cost1;

            // Case 2: finger at j moves to curr
            const cost2 = dp[j] + dist(j, curr);
            if (cost2 < nextDp[prev]) nextDp[prev] = cost2;
        }

        dp = nextDp;
    }

    return Math.min(...dp);
};