Roman to Integer

Patrick Leaton
Published: March 5, 2021, 10:25 p.m.
Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • 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.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3

Example 2:

Input: s = "IV"
Output: 4

Example 3:

Input: s = "IX"
Output: 9

Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

  • 1 <= s.length <= 15
  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

 

Description taken from https://leetcode.com/problems/roman-to-integer/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def romanToInt(self, s: str) -> int:
        translation = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
        output = 0
        for i in range(0, len(s) - 1):
            if translation[s[i]] < translation[s[i+1]]:
                output -= translation[s[i]]
            else:
                output += translation[s[i]]
        return output + translation[s[-1]]

Problem Explanation

Whenever we are translating one value to another, whether it be an order of words or numbers, it may be a good idea to map the translations for easy access.

We can solve this problem by using a translation dictionary to convert Roman numerals to integers, then we can iterate through the string and reference this ordering to decide whether to add or subtract the current number from the output.

We will start by initializing the translation dictionary and converting the Roman values to integers, then initializing the output sum.

        translation = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
        output = 0

 

We will then create a for loop that will stop one index before the end of the string since we are comparing each character with the next character and don't want an index out-of-bounds error.

        for i in range(0, len(s) - 1):

 

We will then start traversing the string and comparing each character with the character next to it.  If the current character is less than the next character, it means we have a number like ‘IX’.  If we encounter this, we can subtract the number we are currently, in this case, ‘I’ or one.  This way, during our next iteration when we add ten, our sum will have a net result of plus nine, "IX". 

            if translation[s[i]] < translation[s[i+1]]:
                output -= translation[s[i]]

 

If the value is greater than the next element, we will just add it to our sum, like "XI".

            else:
                output += translation[s[i]]

 

Our for loop will stop one element before the end of the array to avoid an index out-of-bounds error, so we will need to add the last character as well.

        return output + translation[s[-1]]