难度: Easy
Submission
运行时间: 30 ms
内存: 16.1 MB
class Solution:
def calculateTime(self, keyboard: str, word: str) -> int:
map = {}
for i, c in enumerate(keyboard):
map[c] = i
curr = 0
res = 0
for w in word:
nextkey = map[w]
res += abs(nextkey-curr)
curr = nextkey
return res
Explain
首先，创建一个字典来存储键盘上每个字符的索引，以便快速查找任意字符的位置。然后，初始化一个变量来跟踪当前指针的位置（从键盘的第一个字符开始）。遍历给定的单词中的每个字符，使用字典查找该字符在键盘上的位置，计算从当前位置移动到该字符位置的距离（使用绝对值），并将该距离累加到总移动距离中。更新当前位置为该字符的位置。最终，返回累加的总移动距离。
时间复杂度: O(n + m)
空间复杂度: O(n)
class Solution:
def calculateTime(self, keyboard: str, word: str) -> int:
# 创建一个字典来存储每个键的索引位置
map = {}
for i, c in enumerate(keyboard):
map[c] = i
# 初始化当前指针位置和总移动距离
curr = 0
res = 0
# 遍历单词中的每个字符
for w in word:
nextkey = map[w] # 查找当前字符在键盘上的位置
res += abs(nextkey - curr) # 计算并累加从当前位置到目标位置的距离
curr = nextkey # 更新当前位置
return res
Explore
字典提供了键到值的映射，这使得查找操作非常高效，复杂度为O(1)。在本算法中，需要频繁地查找每个字符在键盘上的位置，使用字典可以快速访问任何字符的索引，从而使得整体算法更加高效。如果使用数组或列表，虽然能以索引快速访问元素，但在这种场景下，我们需要根据字符来获取其索引，这会导致需要遍历数组来查找字符，效率较低。
在实现算法前，应当考虑输入的有效性。对于键盘上不存在的字符，算法可以设计为抛出异常或返回一个错误信息。在代码实现中，可以在查找字典时先检查字符是否存在于字典中，如果不在，可以抛出一个值错误异常（例如，使用`raise ValueError('Character not found on the keyboard')`），确保算法的健壮性。
算法本身对键盘的长度没有特定的限制。因为算法是基于提供的`keyboard`字符串来创建索引映射的，只要`keyboard`字符串中的字符与单词中的字符匹配，算法就能正确运行。无论键盘是标准26个字母的键盘还是包含更多或更少字符的键盘，只要保证单词中的字符都能在键盘字符串中找到，算法就不需要做出调整。
算法的核心部分不需要调整，因为它是根据`keyboard`字符串动态构建字符位置索引的。只要`keyboard`参数正确反映了键盘上字符的当前布局，算法就能正确计算出字符之间的距离。因此，算法已经适配了键盘布局的任何变化，只需要确保传入正确的键盘布局字符串即可。