Сложность: easy
Есть специальная клавиатура, на которой все клавиши расположены в один ряд.
Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.
Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.
Пример:
Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.
👨💻 Алгоритм:
1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.
2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.
3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.
😎 Решение:
class Solution {
public:
int calculateTime(string keyboard, string word) {
vector<int> keyIndices(26, -1);
for (int i = 0; i < keyboard.length(); i++)
keyIndices[keyboard[i] - 'a'] = i;
int prev = 0;
int result = 0;
for (char &c : word) {
result += abs(prev - keyIndices[c - 'a']);
prev = keyIndices[c - 'a'];
}
return result;
}
};Ставь 👍 и забирай 📚 Базу знаний