代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
我们定制了一款特殊的键盘,所有的键都 排列在一行上 。
给定一个长度为 26
的字符串 keyboard
,来表示键盘的布局(索引从 0
到 25
)。一开始,你的手指在索引 0
处。要输入一个字符,你必须把你的手指移动到所需字符的索引处。手指从索引 i
移动到索引 j
所需要的时间是 |i - j|
。
您需要输入一个字符串 word
。写一个函数来计算用一个手指输入需要多少时间。
示例 1:
输入:keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba" 输出:4 解释:从 0 号键移动到 2 号键来输出 'c',又移动到 1 号键来输出 'b',接着移动到 0 号键来输出 'a'。 总用时 = 2 + 1 + 1 = 4.
示例 2:
输入:keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode" 输出:73
提示:
keyboard.length == 26
keyboard
按某种特定顺序排列,并包含每个小写英文字母一次。1 <= word.length <= 104
word[i]
为小写英文字母我们可以用哈希表或者一个长度为 $26$ 的数组 $pos$ 来存储每个字符在键盘上的位置,其中 $pos[c]$ 表示字符 $c$ 在键盘上的位置。
然后我们遍历字符串 $word$,用一个变量 $i$ 记录当前手指所在的位置,初始时 $i = 0$。每次计算当前字符 $c$ 在键盘上的位置 $j$,并将答案增加 $|i - j|$,然后将 $i$ 更新为 $j$。继续遍历下一个字符,直到遍历完整个字符串 $word$。
遍历完字符串 $word$ 之后,即可得到答案。
时间复杂度 $O(n)$,空间复杂度 $O(C)$。其中 $n$ 为字符串 $word$ 的长度;而 $C$ 为字符集大小,本题中 $C = 26$。
class Solution:
def calculateTime(self, keyboard: str, word: str) -> int:
pos = {c: i for i, c in enumerate(keyboard)}
ans = i = 0
for c in word:
ans += abs(pos[c] - i)
i = pos[c]
return ans
class Solution {
public int calculateTime(String keyboard, String word) {
int[] pos = new int[26];
for (int i = 0; i < 26; ++i) {
pos[keyboard.charAt(i) - 'a'] = i;
}
int ans = 0, i = 0;
for (int k = 0; k < word.length(); ++k) {
int j = pos[word.charAt(k) - 'a'];
ans += Math.abs(i - j);
i = j;
}
return ans;
}
}
class Solution {
public:
int calculateTime(string keyboard, string word) {
int pos[26];
for (int i = 0; i < 26; ++i) {
pos[keyboard[i] - 'a'] = i;
}
int ans = 0, i = 0;
for (char& c : word) {
int j = pos[c - 'a'];
ans += abs(i - j);
i = j;
}
return ans;
}
};
func calculateTime(keyboard string, word string) (ans int) {
pos := [26]int{}
for i, c := range keyboard {
pos[c-'a'] = i
}
i := 0
for _, c := range word {
j := pos[c-'a']
ans += abs(i - j)
i = j
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
function calculateTime(keyboard: string, word: string): number {
const pos: number[] = Array(26).fill(0);
for (let i = 0; i < 26; ++i) {
pos[keyboard.charCodeAt(i) - 97] = i;
}
let ans = 0;
let i = 0;
for (const c of word) {
const j = pos[c.charCodeAt(0) - 97];
ans += Math.abs(i - j);
i = j;
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。