Преобразование римских чисел в арабские

Легкая

easy , string , two pointers

12 September 2023

Описание задачи #

Напишите функцию, которая принимает на вход римское число в виде строки и возвращает в ответе ее арабское представление.

Ограничения #

Длина строки с римским числом может быть в диапазоне от 1 до 15
Строка содержит только валидные римские цифры в верхнем регистре

Примеры #

Входные данные: III

Ответ: 3

Объяснение: III = I + I + I = 1 + 1 + 1 = 3
Входные данные: LVIII

Ответ: 58

Объяснение: LVIII = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58
Входные данные: MCMXCIV

Ответ: 1994

Объяснение: MCMXCIV = M + (M - C) + (C - X) + (V - I) = 1000 + (1000 - 100) + (100 - 10) + (5-1) = 1994

Правила формирования римских чисел #

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

Символ	Значение
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Например, 2 записывается как II римскими цифрами, состоящими из двух единиц. 12 записывается как XII, то есть просто X + II. Число 27 записывается как XXVII, то есть XX + V + II. Римские цифры обычно пишутся от большей к меньшей слева направо. Однако цифра 4 — это IIII. Вместо этого 4 записывается как IV. Поскольку единица стоит перед пятеркой, мы вычитаем ее, получая четыре. Тот же принцип применим и к числу 9, которое пишется как IX.

Есть шесть случаев, когда используется вычитание:

I можно поставить перед V и X, чтобы получилось 4 и 9.
X можно поставить перед L и C, чтобы получилось 40 и 90.
C можно поставить перед D и M, чтобы получилось 400 и 900.

Решение #

Для решения данной задачи нам достаточно будет посимвольно пройтись по строке, преобразовать римский цифры в арабские и суммировать их. Главная сложность — учесть правила декремента (IV = 4, а не 6, так как меньшая цифра I стоит перед большей V).

Для преобразования римских цифр создадим хеш-мапу, у которой в качестве ключа будет римская цифра, а в качестве значения арабское число.

var runeToIntegerMap = map[rune]int{
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000,
}

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

var runeToIntegerDecrementsMap = map[rune]map[rune]int{
    'I': {
        'V': 4,
        'X': 9,
    },
    'X': {
        'L': 40,
        'C': 90,
    },
    'C': {
        'D': 400,
        'M': 900,
    },
}

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

Имея эти две вспомогательные хеш-мапы нам останется только пробежаться посимвольно по строке, преобразовать римскую цифру (проверяя не только текущий, но и следующий символ) в число и суммировать получившееся число с переменной-результатом:

package main

var runeToIntegerMap = map[rune]int{
	'I': 1,
	'V': 5,
	'X': 10,
	'L': 50,
	'C': 100,
	'D': 500,
	'M': 1000,
}

var runeToIntegerDecrementsMap = map[rune]map[rune]int{
	'I': {
		'V': 4,
		'X': 9,
	},
	'X': {
		'L': 40,
		'C': 90,
	},
	'C': {
		'D': 400,
		'M': 900,
	},
}

func romanToInt(s string) int {
	res := 0
	runes := []rune(s)

	for i := 0; i < len(runes); i++ {
		if i < len(runes)-1 {
			if possibleDecrements, exist := runeToIntegerDecrementsMap[runes[i]]; exist {
				realNum, found := possibleDecrements[runes[i+1]]
				if found {
					res += realNum
					i++
					continue
				}
			}
		}

		realNum := runeToIntegerMap[runes[i]]
		res += realNum
	}

	return res
}

const runeToIntegerMap: Record<string, number> = {
	'I': 1,
	'V': 5,
	'X': 10,
	'L': 50,
	'C': 100,
	'D': 500,
	'M': 1000,
}

const runeToIntegerDecrementsMap: Record<string, Record<string, number>> = {
	'I': {
		'V': 4,
		'X': 9,
	},
	'X': {
		'L': 40,
		'C': 90,
	},
	'C': {
		'D': 400,
		'M': 900,
	},
}

export const romanToInt = (s: string): number => {
	let res = 0

	for (let i = 0; i < s.length; i++) {
		if (i < s.length - 1) {
			const possibleDecrements = runeToIntegerDecrementsMap[s[i]]

			if (possibleDecrements) {
				const realNum = possibleDecrements[s[i + 1]]

				if (realNum) {
					res += realNum
					i++
					continue
				}
			}
		}

		res += runeToIntegerMap[s[i]]
	}

	return res
}

Оценка сложности #

По времени

Чтобы преобразовать число, нам потребуется проитерироваться по всей строке длиною n. Никаких дополнительных действий, зависящих от длины строки, в алгоритме не происходит. Сложность по времени O(n).

По памяти

Сложность по памяти O(1), так как алгоритм не подразумевает выделение дополнительной памяти, зависящей от длины строки n.

Оригинал задачи на Leetcode

Algorithmics