В этой статье мы подробно разберем решение задачи "Score of a String" с платформы NeetCode. Разберем математическую основу, реализуем оптимальное решение на Java 11, проанализируем сложность и рассмотрим edge cases.
Постановка задачи
Условие:
Дана строка s, состоящая из строчных английских букв. Score строки определяется как сумма абсолютных разниц между ASCII-значениями соседних символов.
Формула:
score(s) = Σ |ASCII(s[i+1]) - ASCII(s[i])| для всех i от 0 до len(s)-2
Пример 1:
Input: s = "code"
Output: 24
Пошаговый расчет:
'c' = 99, 'o' = 111 → |111 - 99| = 12
'o' = 111, 'd' = 100 → |100 - 111| = 11
'd' = 100, 'e' = 101 → |101 - 100| = 1
Итого: 12 + 11 + 1 = 24
Ограничения:
- 2 <= s.length <= 100
- Строка состоит только из строчных английских букв ('a'-'z')
Математическая основа решения
ASCII-коды строчных букв
Важно понимать диапазон значений:
// Строчные буквы в ASCII:
'a' = 97, 'b' = 98, ..., 'z' = 122
// Диапазон: 97-122 (всего 26 букв)
Почему работает преобразование char → int?
В Java при арифметических операциях char автоматически преобразуется в int (его ASCII-код):
char c = 'a';
int ascii = c; // 97
int diff = 'b' - 'a'; // 98 - 97 = 1
Абсолютная разница
Для вычисления разницы между соседними символами используем Math.abs():
int diff = Math.abs('d' - 'o'); // |100 - 111| = 11
Реализация решения на Java 11
Оптимальное решение (O(n) время, O(1) память)
Заключение
Пример, рассмотренный, в статье, можно найти по адресу: https://github.com/ShkrylAndrei/neetcode/blob/main/src/main/java/ScoreOffString/Solution.java