Taken from LeetCode this is a straight forward question that can have multiple correct answers. For my solution I used a map. Here is how I solved it.

The Question

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.

The Solution

We can map each character to its corresponding number. While keeping track of the total summation, we can iterate through the string checking to see if the next mapped character is greater than the current mapped charcter. If the next character is greater, we subtract the current character from the sum. If the current character is greater than the next charcter, then we add it to the sum. Finally we return the final summation.

Here is my code:

def romanToInt(self, s: str) -> int:
    # the conversion mapping
    conversion = {
        'M' : 1000,
        'D' : 500,
        'C' : 100,
        'L' : 50,
        'X' : 10,
        'V' : 5,
        'I' : 1
    num = 0 # final summation
    # if the string is only one character long, convert that character and return it
    if len(s) ==  1: 
        return conversion[s[0]]
    for i, l in enumerate(s[:-1]): # where i is the iterator and l is the current letter, loop until length - 1
        if conversion[l] < conversion[s[i + 1]]: # if the current converted letter is less than the next converted letter
            num -= conversion[l] # subtract the current converted letter from the sum
            num += conversion[l] # else add the current converted letter to the sum
    # since it only loops until the length - 1, add on the final elemenet and return
    return num + conversion[s[-1]]

The Algorithm

Let S be a string of roman numerals such that s1, s2, s3, ..., sn is the single-character roman numerals of S.

While keeping track of total summation sum iterate from s1 to sn - 1, such that the current iteration of i is the numerical value its roman numeral counterpart.

  • If i > i + 1, sum += i
  • Else sum -= i.

Return sum + sn.

Runtime Complexity

The runtime will be O(n), since you only iterate over the string once.