1320. 使用双指最少移动距离

Hard

题目描述

你有一个如上图所示的键盘布局，其中每个英文大写字母都位于某个坐标上。

例如，字母 ‘A’ 位于坐标 (0, 0)，字母 ‘B’ 位于坐标 (0, 1)，字母 ‘P’ 位于坐标 (2, 3)，字母 ‘Z’ 位于坐标 (4, 1)。

给定字符串 word，返回仅使用两根手指输入该字符串的最小总距离。

坐标 (x1, y1) 和 (x2, y2) 之间的距离是 |x1 - x2| + |y1 - y2|。

注意，两根手指的初始位置被认为是免费的，所以不计入你的总距离，同时你的两根手指不必从第一个字母或前两个字母开始。

示例 1：

输入：word = "CAKE"
输出：3
解释：使用两根手指，输入 "CAKE" 的一种最优方式是：
手指 1 在字母 'C' 上 -> 成本 = 0
手指 1 在字母 'A' 上 -> 成本 = 从字母 'C' 到字母 'A' 的距离 = 2
手指 2 在字母 'K' 上 -> 成本 = 0
手指 2 在字母 'E' 上 -> 成本 = 从字母 'K' 到字母 'E' 的距离 = 1
总距离 = 3

示例 2：

输入：word = "HAPPY"
输出：6
解释：使用两根手指，输入 "HAPPY" 的一种最优方式是：
手指 1 在字母 'H' 上 -> 成本 = 0
手指 1 在字母 'A' 上 -> 成本 = 从字母 'H' 到字母 'A' 的距离 = 2
手指 2 在字母 'P' 上 -> 成本 = 0
手指 2 在字母 'P' 上 -> 成本 = 从字母 'P' 到字母 'P' 的距离 = 0
手指 1 在字母 'Y' 上 -> 成本 = 从字母 'A' 到字母 'Y' 的距离 = 4
总距离 = 6

约束条件：

2 <= word.length <= 300
word 由大写英文字母组成

解题思路

这是一道经典的动态规划问题。核心思路是跟踪两根手指的位置状态。

基本思路： 首先需要建立字母到坐标的映射，键盘布局是6行5列的网格，可以通过字母的ASCII值计算出坐标位置。

状态定义： 使用三维动态规划 dp[i][j][k] 表示当一根手指在第 i 个字符位置，另一根手指在第 j 个字符位置时，已经输入前 k 个字符的最小移动距离。

状态转移： 对于每个新字符，我们有两个选择：

使用手指1移动到新位置，手指2保持不变
使用手指2移动到新位置，手指1保持不变

为了优化空间复杂度，可以使用二维数组滚动更新，因为当前状态只依赖于前一个状态。

边界处理： 初始时两根手指可以免费放置在任意位置，所以前两个字符的放置成本为0。

推荐解法： 使用二维DP优化的版本，既节省空间又保持代码简洁性。时间复杂度O(n²)，空间复杂度O(n)。

代码实现

class Solution {
public:
    int minimumDistance(string word) {
        int n = word.length();
        if (n == 0) return 0;
        
        auto getPos = [](char c) -> pair<int, int> {
            int idx = c - 'A';
            return {idx / 6, idx % 6};
        };
        
        auto getDist = [&](char a, char b) -> int {
            auto [x1, y1] = getPos(a);
            auto [x2, y2] = getPos(b);
            return abs(x1 - x2) + abs(y1 - y2);
        };
        
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        
        // 初始化：前两个字符可以免费放置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 1) {
                    dp[i][j] = 0;
                }
            }
        }
        
        for (int k = 2; k < n; k++) {
            vector<vector<int>> newDp(n, vector<int>(n, INT_MAX));
            
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    if (dp[i][j] == INT_MAX) continue;
                    
                    // 手指1移动到新位置k，手指2保持在j
                    newDp[k][j] = min(newDp[k][j], dp[i][j] + getDist(word[i], word[k]));
                    
                    // 手指2移动到新位置k，手指1保持在i
                    newDp[i][k] = min(newDp[i][k], dp[i][j] + getDist(word[j], word[k]));
                }
            }
            dp = newDp;
        }
        
        int result = INT_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result = min(result, dp[i][j]);
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        if n == 0:
            return 0
        
        def get_pos(c):
            idx = ord(c) - ord('A')
            return (idx // 6, idx % 6)
        
        def get_dist(a, b):
            x1, y1 = get_pos(a)
            x2, y2 = get_pos(b)
            return abs(x1 - x2) + abs(y1 - y2)
        
        dp = [[float('inf')] * n for _ in range(n)]
        
        # 初始化：前两个字符可以免费放置
        for i in range(n):
            for j in range(n):
                if i == 0 or j == 1:
                    dp[i][j] = 0
        
        for k in range(2, n):
            new_dp = [[float('inf')] * n for _ in range(n)]
            
            for i in range(k):
                for j in range(k):
                    if dp[i][j] == float('inf'):
                        continue
                    
                    # 手指1移动到新位置k，手指2保持在j
                    new_dp[k][j] = min(new_dp[k][j], dp[i][j] + get_dist(word[i], word[k]))
                    
                    # 手指2移动到新位置k，手指1保持在i
                    new_dp[i][k] = min(new_dp[i][k], dp[i][j] + get_dist(word[j], word[k]))
            
            dp = new_dp
        
        result = float('inf')
        for i in range(n):
            for j in range(n):
                result = min(result, dp[i][j])
        
        return result

public class Solution {
    public int MinimumDistance(string word) {
        int n = word.Length;
        if (n == 0) return 0;
        
        (int, int) GetPos(char c) {
            int idx = c - 'A';
            return (idx / 6, idx % 6);
        }
        
        int GetDist(char a, char b) {
            var (x1, y1) = GetPos(a);
            var (x2, y2) = GetPos(b);
            return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
        }
        
        int[,] dp = new int[n, n];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = int.MaxValue;
                if (i == 0 || j == 1) {
                    dp[i, j] = 0;
                }
            }
        }
        
        for (int k = 2; k < n; k++) {
            int[,] newDp = new int[n, n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    newDp[i, j] = int.MaxValue;
                }
            }
            
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    if (dp[i, j] == int.MaxValue) continue;
                    
                    // 手指1移动到新位置k，手指2保持在j
                    newDp[k, j] = Math.Min(newDp[k, j], dp[i, j] + GetDist(word[i], word[k]));
                    
                    // 手指2移动到新位置k，手指1保持在i
                    newDp[i, k] = Math.Min(newDp[i, k], dp[i, j] + GetDist(word[j], word[k]));
                }
            }
            dp = newDp;
        }
        
        int result = int.MaxValue;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result = Math.Min(result, dp[i, j]);
            }
        }
        
        return result;
    }
}

var minimumDistance = function(word) {
    const getPos = (char) => {
        const code = char.charCodeAt(0) - 65;
        return [Math.floor(code / 6), code % 6];
    };
    
    const getDist = (char1, char2) => {
        const [x1, y1] = getPos(char1);
        const [x2, y2] = getPos(char2);
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    };
    
    const n = word.length;
    const memo = new Map();
    
    const dp = (i, left, right) => {
        if (i === n) return 0;
        
        const key = `${i},${left},${right}`;
        if (memo.has(key)) return memo.get(key);
        
        const char = word[i];
        let result = Infinity;
        
        if (left === -1) {
            result = Math.min(result, dp(i + 1, i, right));
        } else {
            result = Math.min(result, getDist(word[left], char) + dp(i + 1, i, right));
        }
        
        if (right === -1) {
            result = Math.min(result, dp(i + 1, left, i));
        } else {
            result = Math.min(result, getDist(word[right], char) + dp(i + 1, left, i));
        }
        
        memo.set(key, result);
        return result;
    };
    
    return dp(0, -1, -1);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n³)	外层循环n次，内层双重循环最多n²次
空间复杂度	O(n²)	需要n×n的二维数组存储状态

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目