Problem Statement in English

You’re given a string s representing a Roman numeral. Convert s to an integer.

Approach

This problem becomes a lot easier if we could just add up the values of the Roman numerals as we iterated.

However, there are some cases where we need to subtract instead of add. For example, “IV” is 4, not 6.

To handle this, we can replace all instances of “IV” with “IIII”, “IX” with “VIIII”, “XL” with “XXXX”, “XC” with “LXXXX”, “CD” with “CCCC”, and “CM” with “DCCCC”. This way, we can just sum up the values of the characters in the string.

After this we can use a dictionary to map each Roman numeral to its integer value and iterate through the string, summing up the values.

And we’re done!

Solution in Python


class Solution:
    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        number = 0
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
        s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
        s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
        for char in s:
            number += translations[char]
        return number

Complexity

  • Time: $O(n)$
    Since we are iterating through the string s once, the time complexity is linear with respect to the length of the string.

  • Space: $O(1)$
    Since we are using a dictionary of fixed size and not using any additional data structures that scale with input size, the space complexity is constant.

Mistakes I Made

My implementation wasn’t anywhere as elegant as this.

And we are done.