[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法
2021/10/11 6:16:13
本文主要是介绍[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
LeetCode原题链接:1320. Minimum Distance to Type a Word Using Two Fingers
You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate.
- For example, the letter
'A'
is located at coordinate(0, 0)
, the letter'B'
is located at coordinate(0, 1)
, the letter'P'
is located at coordinate(2, 3)
and the letter'Z'
is located at coordinate(4, 1)
.
Given the string word
, return the minimum total distance to type such string using only two fingers.
The distance between coordinates (x1, y1)
and (x2, y2)
is |x1 - x2| + |y1 - y2|
.
Note that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.
Example 1:
Input: word = "CAKE" Output: 3 Explanation: Using two fingers, one optimal way to type "CAKE" is: Finger 1 on letter 'C' -> cost = 0 Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 Finger 2 on letter 'K' -> cost = 0 Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 Total distance = 3
Example 2:
Input: word = "HAPPY" Output: 6 Explanation: Using two fingers, one optimal way to type "HAPPY" is: Finger 1 on letter 'H' -> cost = 0 Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2 Finger 2 on letter 'P' -> cost = 0 Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0 Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4 Total distance = 6
Example 3:
Input: word = "NEW" Output: 3
Example 4:
Input: word = "YEAR" Output: 7
Constraints:
2 <= word.length <= 300
word
consists of uppercase English letters.
题目分析
刚看到这道题的时候还真是有点懵,想了半天两根手指怎么交叉同时输入两个相隔很远的字母呢...(第一反应两根手指是一只手上相邻的两根手指
这篇关于[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享