Breaking Down the 'Roman to Integer' Puzzle in Python

Introduction

In this brief guide, we'll walk through a simple solution to the 'Roman to Integer' problem in Python.

Feel free to follow along with me, and give the problem a try yourself!

Problem Statement

Given a roman numeral string, convert it to an integer.

What might pose a bit of difficulty are the special cases within roman numerals:

• I can be placed before V (5) and X (10) to make 4 and 9. 

• X can be placed before L (50) and C (100) to make 40 and 90. 

• C can be placed before D (500) and M (1000) to make 400 and 900.

Process

The best way to approach this sort of problem is to map out your ideas through comments:

class Solution:
    def romanToInt(self, s: str) -> int:
		// create a dictionary mapping each numeral to a value
		// loop over the string
		// sum together each character's respective value
		// return sum

Implementing the dictionary and loop was straightforward enough, but what came as a bit of trouble was adding together each character...

Because of those special cases, something like this would unfortunately not work:

class Solution:
    def romanToInt(self, s: str) -> int:
		// create a dictionary mapping each numeral to a value
		numVals = {
				'I':1, 
				'V':5, 
				'X':10, 
				'L':50, 
				'C':100, 
				'D':500, 
				'M':1000
				}

		// initialize sum variable 
		sum = 0

		// loop over the string
		for symbol in s:
			// sum together each character's respective value
			sum += numVals[symbol]

		// return sum
		return sum

Instead, it's essential that we reverse the original string.

Now, starting at the beginning of the reversed string, we can check if the current character is greater or lesser than the previous, and add or subtract the current value, respectively.

This wouldn't work on an un-reversed string since you would have to perform multiple checks in a row (and it just gets messy).

class Solution:
    def romanToInt(self, s: str) -> int:
		// create a dictionary mapping each numeral to a value
		numVals = {
				'I':1, 
				'V':5, 
				'X':10, 
				'L':50, 
				'C':100, 
				'D':500, 
				'M':1000
				}

		// initialize sum, prev variables
		sum = 0
		prev = 0
		
		// reverse string
		// empty colons indicate that we start at the beginning 
		// and end at the end of the string
		// -1 means going backwards in increments of -1
		sRev = s[::-1]

		// loop over the reversed string
		for symbol in sRev:
			// sum together each character's respective value
			if numVals[symbol] >= prev:
                sum += numVals[symbol]
            	else:
                sum -= numVals[symbol]

            	// update prev
            	prev = numVals[symbol]

		// return sum
		return sum

Final Thoughts

Thanks for reading!