3846. 使用单指输入字符串的总距离 🔒

题目描述

有一个特殊的键盘，其按键排列成如下矩形网格。

q	w	e	r	t	y	u	i	o	p
a	s	d	f	g	h	j	k	l
z	x	c	v	b	n	m

给定一个只包含小写英文字母的字符串 s。返回一个整数，表示使用仅一个手指输入字符串 s 的总距离。手指初始位置在字母键 'a' 上。

两个位于 (r1, c1) 和 (r2, c2) 的按键距离是 |r1 - r2| + |c1 - c2|。

示例 1：

输入：s = "hello"

输出：17

解释：

你的手指从 'a' 开始，位于 (1, 0)。
移动到 'h'，位于 (1, 5)。距离是 |1 - 1| + |0 - 5| = 5。
移动到 'e'，位于 (0, 2)。距离是 |1 - 0| + |5 - 2| = 4。
移动到 'l'，位于 (1, 8)。距离是 |0 - 1| + |2 - 8| = 7。
移动到 'l'，位于 (1, 8)。距离是 |1 - 1| + |8 - 8| = 0。
移动到 'o'，位于 (0, 8)。距离是 |1 - 0| + |8 - 8| = 1。
总距离是 5 + 4 + 7 + 0 + 1 = 17。

示例 2：

输入：s = "a"

输出：0

解释：

你的手指从 'a' 开始，位于 (1, 0)。
移动到 'a'，位于 (1, 0)。距离是 |1 - 1| + |0 - 0| = 0。
总距离为 0。

提示：

1 <= s.length <= 10⁴
s 只包含小写英文字母。

解法

方法一：模拟

我们定义一个哈希表 \(\textit{pos}\)，用来存储每个字符在键盘上的位置。对于字符串 \(s\) 中的每个字符，我们计算从上一个字符到当前字符的距离，并将其累加到答案中。最后返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是字符集，这里是 26 个小写英文字母。

Python3JavaC++GoTypeScript

pos = {}
keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
for (i, row) in enumerate(keys):
    for (j, key) in enumerate(row):
        pos[key] = (i, j)


class Solution:
    def totalDistance(self, s: str) -> int:
        pre = 'a'
        ans = 0
        for cur in s:
            x1, y1 = pos[pre]
            x2, y2 = pos[cur]
            dist = abs(x1 - x2) + abs(y1 - y2)
            ans += dist
            pre = cur
        return ans

class Solution {
    private static final Map<Character, int[]> pos = new HashMap<>();

    static {
        String[] keys = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        for (int i = 0; i < keys.length; i++) {
            for (int j = 0; j < keys[i].length(); j++) {
                pos.put(keys[i].charAt(j), new int[] {i, j});
            }
        }
    }

    public int totalDistance(String s) {
        char pre = 'a';
        int ans = 0;

        for (char cur : s.toCharArray()) {
            int[] p1 = pos.get(pre);
            int[] p2 = pos.get(cur);
            ans += Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
            pre = cur;
        }

        return ans;
    }
}

class Solution {
public:
    int totalDistance(string s) {
        static unordered_map<char, pair<int, int>> pos = [] {
            unordered_map<char, pair<int, int>> m;
            vector<string> keys = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
            for (int i = 0; i < keys.size(); ++i) {
                for (int j = 0; j < keys[i].size(); ++j) {
                    m[keys[i][j]] = {i, j};
                }
            }
            return m;
        }();

        char pre = 'a';
        int ans = 0;

        for (char cur : s) {
            auto [x1, y1] = pos[pre];
            auto [x2, y2] = pos[cur];
            ans += abs(x1 - x2) + abs(y1 - y2);
            pre = cur;
        }

        return ans;
    }
};

var pos map[byte][2]int

func init() {
    pos = make(map[byte][2]int)
    keys := []string{"qwertyuiop", "asdfghjkl", "zxcvbnm"}
    for i, row := range keys {
        for j := 0; j < len(row); j++ {
            pos[row[j]] = [2]int{i, j}
        }
    }
}

func totalDistance(s string) int {
    pre := byte('a')
    ans := 0

    for i := 0; i < len(s); i++ {
        cur := s[i]
        p1 := pos[pre]
        p2 := pos[cur]
        ans += abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
        pre = cur
    }

    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

const pos: Record<string, [number, number]> = {};

const keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm'];
keys.forEach((row, i) => {
    [...row].forEach((key, j) => {
        pos[key] = [i, j];
    });
});

function totalDistance(s: string): number {
    let pre = 'a';
    let ans = 0;

    for (const cur of s) {
        const [x1, y1] = pos[pre];
        const [x2, y2] = pos[cur];
        ans += Math.abs(x1 - x2) + Math.abs(y1 - y2);
        pre = cur;
    }

    return ans;
}

3846. 使用单指输入字符串的总距离 🔒

题目描述

解法

方法一：模拟

评论