Пример решения задачи #13. Python LeetCode, Roman to Integer

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Roman to Integer.
Сложность: Легкая.
Статус решения: "Решено".

Условие задачи:
Римские цифры представлены семью разными символами: I, V, X, L, C, D и M.

Symbol: I, Value: 1.
Symbol: V, Value: 5.
Symbol: X, Value: 10.
Symbol: L, Value: 50.
Symbol: C, Value: 100.
Symbol: D, Value: 500.
Symbol: M, Value: 1000.

Например, 2 записывается как II римскими цифрами, состоящими из двух единиц. 12 записывается как XII, то есть просто X + II. Число 27 записывается как XXVII, то есть XX+V+II.

Римские цифры обычно пишутся от большего к меньшему слева направо. Однако цифра для четырех не IIII. Вместо этого число четыре записывается как IV. Поскольку единица стоит перед пятью, мы вычитаем ее, получая четыре. Тот же принцип применим к числу девять, которое записывается как IX. Существует шесть случаев, когда используется вычитание:

I можно поместить перед V(5) и X(10), чтобы получить 4 и 9.
X можно поместить перед L(50) и C(100), чтобы получить 40 и 90.
C можно разместить перед D(500) и M(1000), чтобы получить 400 и 900.
Преобразуйте римские цифры в целое число.

Решение:

Python

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        # Создаем словарь для соответствия арабских цифр и римских символов
        roman_to_int = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        
        # Переменная для хранения результата
        num = 0

        # Переменная для хранения значения предыдущего символа
        # Это поможет определить, нужно ли прибавлять или вычитать текущее значение
        prev_value = 0

        # Обрабатываем строку в обратном порядке (справа налево)
        for char in s[::-1]:

         # Получаем числовое значение текущего римского символа
         current_value = roman_to_int[char]

            # Если текущее значение меньше предыдущего, вычитаем его из результата
            if current_value < prev_value:
                num -= current_value
            else:
            # В остальных случаях прибавляем значение
                num += current_value

            # Обновляем значение предыдущего символа
            prev_value = current_value

        # Возвращаем итоговое число
        return num

Объяснение кода

Словарь roman_to_int:
Создаем словарь, где ключи - это римские цифры, а значения - соответствующие арабские числа.

Инициализация переменных:
num - будет хранить итоговое число.
prev_value - будет хранить значение предыдущего символа для определения, нужно ли вычитать или добавлять текущее значение.

Итерация по строке в обратном порядке:
Проходим по строке с римским числом справа налево. Это важно, так как вычитание происходит только для символов, стоящих перед большими по значению символами.

Сравнение значений:
Если текущее значение меньше предыдущего, то мы вычитаем его из num (это случай, когда используется вычитание для представления чисел 4, 9, 40 и т.д.).

Иначе, мы просто добавляем текущее значение к num.

Обновление prev_value:
После каждой итерации обновляем prev_value, чтобы использовать его для сравнения на следующем шаге.

Возврат результата:
После обработки всех символов в строке, в переменной num будет содержаться итоговое арабское число.

Почему начинаем с конца?
Идея идти с конца заключается в том, что вычитание в римских цифрах происходит только когда меньший символ стоит перед большим. Идя с конца, мы всегда сравниваем текущий символ с предыдущим, который уже был обработан. Таким образом, мы можем точно определить, нужно ли вычитать или добавлять текущее значение.

Источник решения: hdhai.com