二指输入的的最小距离

标签: 字符串 动态规划

难度: Hard

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。

  • 例如字母 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[i] 都是一个大写英文字母。

Submission

运行时间: 85 ms

内存: 16.0 MB

class Solution:
    def minimumDistance(self, word: str) -> int:
        L=len(word)
        def get_dis(p1,p2):
            x1,y1=p1//6,p1%6
            x2,y2=p2//6,p2%6
            return abs(x1-x2)+abs(y1-y2)
        Max=L*20
        f=[[0]*26,[Max]*26]
        ordA=ord('A')
        # ord0=ord(word[0])-ordA
        # f[ord0]=0
        for i in range(1,L):
            pre=ord(word[i-1])-ordA
            cur=ord(word[i])-ordA
            dis=get_dis(pre,cur)
            for j in range(26):
                f[1][j]=f[0][j]+dis
                if pre==j:
                    for k in range(26):
                        dk=get_dis(k,cur)
                        f[1][j]=min(f[1][j],f[0][k]+dk)
            f[0],f[1]=f[1],f[0]
        return min(f[0])

Explain

这个题解采用了动态规划方法来解决两指输入最小距离问题。每个字母在键盘上对应一个坐标，通过坐标可以计算两个字母之间的曼哈顿距离。动态规划的状态f[i][j]表示在考虑到第i个字母时，一个手指在word[i]，另一个手指在j位置时的最小移动距离。这里用了两个数组，f[0]和f[1]，交替代表当前和前一步的状态，以减少空间消耗。对于每个字母，我们考虑保持一个手指的位置不变，移动另一个手指，以及交换这两个手指的角色。最后返回最后一个字母时的最小移动距离。

时间复杂度: O(L*26^2)

空间复杂度: O(26)

class Solution:
    def minimumDistance(self, word: str) -> int:
        L=len(word) # 字符串长度
        def get_dis(p1,p2): # 计算键盘上两个字母之间的曼哈顿距离
            x1,y1=p1//6,p1%6
            x2,y2=p2//6,p2%6
            return abs(x1-x2)+abs(y1-y2)
        Max=L*20 # 设置一个足够大的数，作为初始的最大距离
        f=[[0]*26,[Max]*26] # 动态规划数组，交替存储当前和前一步的状态
        ordA=ord('A') # A的ASCII码，后面用于计算其他字母的位置
        for i in range(1,L): # 遍历字符串中的每个字符
            pre=ord(word[i-1])-ordA # 前一个字符的位置
            cur=ord(word[i])-ordA # 当前字符的位置
            dis=get_dis(pre,cur) # 计算两个连续字母间的距离
            for j in range(26): # 更新动态规划数组
                f[1][j]=f[0][j]+dis
                if pre==j:
                    for k in range(26): # 考虑两指交换位置
                        dk=get_dis(k,cur)
                        f[1][j]=min(f[1][j],f[0][k]+dk)
            f[0],f[1]=f[1],[Max]*26 # 交换数组，准备下一次迭代
        return min(f[0]) # 返回最小的距离

Explore

在题解中，动态规划数组f[i][j]是用来计算和存储到达第i个字母时的最小移动距离，其中i表示当前处理到word字符串中的第i个字母。数组的第二个维度j则代表26个英文字母中的一个，具体来说，f[i][j]存储的是在处理到第i个字母时，假设一个手指位于当前字母word[i]，另一个手指位于字母j的位置时，达到这种状态的最小移动距离。通过这种表示方法，我们可以动态地计算每一步的最优移动策略，最终求得整个字符串输入的最小距离。

在动态规划中使用两个数组f[0]和f[1]交替存储状态是为了优化空间复杂度和避免在更新过程中出现数据覆盖的问题。如果使用单一数组进行状态更新，那么在计算当前状态时，前面的状态可能会被覆盖，导致无法正确引用前一状态的数据。通过使用两个数组交替，我们可以保持前一状态的数据不被覆盖直到这一轮计算完毕，从而保证每一步状态计算的正确性。这种方法还有助于减少内存消耗，因为我们只需要维护两个长度为26的数组，而不是为每一个字符位置都维护一个数组。

在题解中使用的数字6来自于假设的键盘布局，其中键盘被假设为一个6列的矩阵（例如，可以是5行6列的矩阵，总共30个键位足以容纳26个英文字母）。通过这种布局，使用p1//6可以计算出字母在键盘矩阵中的行位置，而p1%6则用于计算列位置。这样的坐标计算方法是基于将26个字母映射到一个5行6列的键盘布局上，每个字母对应一个唯一的坐标位置，从而可以通过曼哈顿距离公式计算任意两个字母之间的距离。