1 Star 0 Fork 332

peaking / leetcode

forked from doocs / leetcode 
加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
README.md 4.22 KB
一键复制 编辑 原始数据 按行查看 历史
ylb 提交于 2024-02-21 08:52 . feat: add problem tags (#2361)

1165. 单行键盘

English Version

题目描述

我们定制了一款特殊的键盘,所有的键都 排列在一行上 。

给定一个长度为 26 的字符串 keyboard ,来表示键盘的布局(索引从 025 )。一开始,你的手指在索引 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;
}
Java
1
https://gitee.com/peaklee1134/leetcode.git
git@gitee.com:peaklee1134/leetcode.git
peaklee1134
leetcode
leetcode
main

搜索帮助