Roman To Integer

String Math

Problem

Given a roman numeral, convert it to an integer.

For example:

Input: s = "III"
Output: 3

Input: s = "IV"
Output: 4

Input: s = "IX"
Output: 9

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

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

Thought Process

• We can use a dictionary to map the corresponding roman numerals to their numbers

• To handle the case where a smaller roman numeral is placed before a larger one (which results in a subtraction), we need to subtract the previous number twice

  • Need to subtract twice because we are taking that number away from the count (which we added to it before) and then we subtract again because of the normal roman numeral rule where you subtract the lesser number from the higher one.

Solution

class Solution:
    def romanToInt(self, s: str) -> int:
        count = 0
        
        d = {"I":1, "V": 5, "X":10, "L": 50, "C": 100, "D": 500, "M":1000}
        
        for i in range(len(s)):
            if i > 0 and d[s[i-1]] < d[s[i]]:
                count-=d[s[i-1]]
                count+= d[s[i]] - (d[s[i-1]])
            else:
                count+=d[s[i]]
        return count
            
        

Key Points

• For the current roman numeral, if the previous roman numeral is of a lesser number then we have to subtract the previous roman numeral twice from the count

Time Complexity

• Time: $O(n)$

• Space: $O(1)$