Published on

Roman Numeral To Integer

  • avatar
    David Gordon


Exploring an easy leetcode programming problem.

Problem Statement

The problem is stated as follows:

Given a string that represents a roman numeral,
e.g. 'III', convert it to an integer.

I've left certain details out for the sake of brevity, but they can be accessed through the leetcode link above. These are the standard numerals in what we may call the 'Roman Numeral Language':

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

One trick to remember is that before a numeral, you can place the previous decimal numeral (e.g. 1, 10, 100, 1000) in front of it to achieve a one less than expression.

IV = 4
IX = 9
XL = 40
XC = 90
CD = 400
CM = 900


We can treat this as a parsing problem, wherein we tokenize the input string and parse the tokens into the result. As an added bonus, we don't need to make any special cases for the addional one less than situations if we include them in our set of tokens and use a look-ahead check.

Using that design, we have the following tokens:

token_map = {
	"I": 1,
	"IV": 4,
	"V": 5,
	"IX": 9,
	"X": 10,
	"XL": 40,
	"L": 50,
	"XC": 90,
	"C": 100,
	"CD": 400,
	"D": 500,
	"CM": 900,
	"M": 1000

I've represented these as a python dictionary as that's what I'll present the solution in. I've chosen to simply map the token to their respective integer value. We can then just iterate through the string input and accumulate a resultant integer using this token map.

def solution (input_string: str) -> int:
	result, index = 0
	while index < len(input_string)
		if index = 1 < len(input_string) and input_string[index: index + 2] in token_map:
			result += token_map[input_string[index: index + 2]]
			index += 2
		result += token_map[input_string[index]]
		index += 1
	return result

This is a fairly straightforward solution that runs in O(n)O(n) time complexity.