Leetcode 1320:二指输入的的最小距离(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1320:二指输入的的最小距离(超详细的解法!!!)

in leetcode with 0 comment

二指输入法定制键盘在 XY 平面上的布局如上图所示,其中每个大写英文字母都位于某个坐标处,例如字母 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

示例 3:

输入:word = "NEW"
输出:3

示例 4:

输入:word = "YEAR"
输出:7 

提示:

解题思路

这个问题使用递归加记忆化最好理解。我们可以定义函数$f(k_1,k_2,u)$表示当前第一个手指在$k_1$位置,第二个手指在$k_2$位置,当前遍历到单词的第u-1位时的最小距离。那么接下来我们需要考虑第u位字符是第一手指移过去还是第二个手指移过去。

其中dis表示计算曼哈顿距离,而coor[t]表示字符t的坐标,最后结果就是二者的最小值。代码也非常简洁:

from functools import lru_cache
class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        mat = collections.defaultdict(list)
        for i in range(5):
            for j in range(6):
                mat[chr((i * 6 + j) + 65)] = (i, j)
        
        @lru_cache(None)
        def dis(a, b):
            return abs(a[0] - b[0]) + abs(a[1] - b[1])
        
        @lru_cache(None)
        def dfs(f1, f2, u):
            if u == n:
                return 0
            
            target = mat[word[u]]
            r1 = dis(f1, target) + dfs(target, f2, u + 1)
            r2 = (dis(f2, target) if f2 else 0) + dfs(f1, target, u + 1)
            return min(r1, r2)
        return dfs(mat[word[0]], None, 1)

需要注意的是第一个手指起手和第二个手指起手都是一样的,但是我们在中间过程中需要判断手指坐标是不是空(因为一个起手,另一就空着)。

同理,我们可以将上面的过程通过动态规划来实现,思路是一样的(由于是最短路问题,所以这里也可以理解为bfs思路)。这里我们有一个处理坐标的trick

def dis(a, b):
    if a == 26:
        return 0
    return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)

需要注意的是,在两个手指都没有放的情况下,此时包含了一种状态,我们通过26表示这种状态。

from functools import lru_cache
class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        
        @lru_cache(None)
        def dis(a, b):
            if a == 26:
                return 0
            return abs(a//6 - b//6) + abs(a%6 - b%6)
        
        dp = collections.defaultdict(int)
        for k in range(n):
            u = ord(word[k]) - 65
            for i in range(27):
                for j in range(27):
                    dp[i, j, k] = min(dp[u, j, k - 1] + dis(i, u), dp[i, u, k - 1] + dis(j, u))
        return dp[26, 26, n - 1]    

采用bfs的思路去写,我们遍历的每个字符就是图中的一层。

from functools import lru_cache
class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        
        @lru_cache(None)
        def dis(a, b):
            return a and abs(a//6 - b//6) + abs(a%6 - b%6)
        
        dp = {(0, 0): 0}
        for k in range(n):
            u = ord(word[k]) + 1
            tmp = {}
            for a, b in dp:
                tmp[a, u] = min(tmp.get((a, u), 3000), dp[a, b] + dis(b, u))
                tmp[u, b] = min(tmp.get((u, b), 3000), dp[a, b] + dis(a, u))
            dp = tmp
        return min(dp.values())  

注意上面代码中,我们的dis换了一种写法,此时我们通过0表示手指没有放入的状态(这种写法更加简洁)。这个代码相较于前面的代码优化了空间复杂度。实际上我们可以将空间复杂度优化成一维,怎么做呢?

如果我们只有一个手指来完成键入的话,那么此时的移动距离一定是最大的(两个手指键入的情况下)。当加入一个手指输入后,移动距离必然会减小,那么我们只需要这个减小的距离越大越好就行啦!

我们可以定义函数$f(x)$表示键入x后可以减少的最大移动距离。假设我们左手指放在a的位置(右手指在b的位置),现在需要键入下一个字符c,如果不用右手指的话,此时的移动距离就是dis(a, c),使用右手指的话移动距离就是dis(b, c),也就是减少了dis(a, c) - dis(b, c)的移动距离。

最后的结果就是所有字符的曼哈顿距离减去$f$的最大值即可。

from functools import lru_cache
class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        
        @lru_cache(None)
        def dis(a, b):
            return abs(a//6 - b//6) + abs(a%6 - b%6)
        
        A = [ord(c) - 65 for c in word]
        dp = [0] * 26
        for i in range(n - 1):
            b, c = A[i], A[i + 1]
            dp[b] = max(dp[a] + dis(b, c) - dis(a, c) for a in range(26))
        return sum(dis(A[i], A[i + 1]) for i in range(n - 1)) - max(dp)

reference:

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/477652/JavaC%2B%2BPython-1D-DP-O(1)-Space

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses