LC013 - Roman to Integer

Problem

You get a string (array of chars) of Roman numerics and have to convert it into an integer.

Example

Input: s = “XVII”

Output: 17

Glossary

• I = 1

• V = 5

• X = 10

• L = 50

• C = 100

• D = 500

• M = 1000

I can be placed before V and X to make 4 and 9. X can be placed before L and C to make 40 and 90. C can be placed before D and M to make 400 and 900.

Solution

Naive

Use an if-else or match case to check the value of the char at the current string index, then check the char value at the next index if the current index is I, X, or C.

The time complexity of this implementation is $\text{O}(N)$, and there is no additional memory usage.

def romanToInt(s: str) -> int:
	retVal = 0
	for i, n in enumerate(s):
		if n == "I":
			if i+1 < len(s):
				if s[i+1] == "V" or s[i+1] == "X":
					retVal -= 1
				else:
					retVal += 1
			else:
				retVal += 1
		elif n == "V":
			retVal += 5
		elif n == "X":
			if i+1 < len(s):
				if s[i+1] == "L" or s[i+1] == "C":
					retVal -= 10
				else:
					retVal += 10
			else:
				retVal += 10
		elif n == "L":
				retVal += 50
		elif n == "C":
			if i+1 < len(s):
				if s[i+1] == "D" or s[i+1] == "M":
					retVal -= 100
				else:
					retVal += 100
			else:
				retVal += 100
		elif n == "D":
			retVal += 500
		elif n == "M":
			retVal += 1000

	return retVal

Map

This has the same performance as the previous version, just more concise and readable

def romanToInt(s: str) -> int:
		map = { "I" : 1,
						"V" : 5,
						"X" : 10,
						"L" : 50,
						"C" : 100,
						"D" : 500,
						"M" : 1000
					}
		
		retVal = 0
		
		for i, n in enumerate(s):
				if i+1 < len(s) and map[s[i]] < map[s[i+1]]:
						# Subtraction
						retVal -= map[n]
				else:
						# Addition
						retVal += map[n]
			
		return retVal