13_Roman to Integer

[easy]

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Roman rules:

M = 1000

D = 500

C = 100

L = 50

X = 10

V = 5

I = 1

Special cases to pay attention:

CM = 900

CD = 400

XC = 90

XL = 40

IX = 9

IV = 4

Idea

• Store the roman rules in a dictionary, whose keys are the letters and values are the corresponding numbers.

• Loop over each letter in the string except the last one. If the current number is less than the next, then subtract this number. Otherwise add this number.

• Add the last number.

Complexity

• Time: $O(n)$

• Space: $O(1)$

Solution

def romanToInt(s):
    """
    :type s: str
    :rtype: int
    """
    # define the integer output
    out = 0

    # define the roman rule
    roman = {"M":1000, "D":500, "C":100, "L":50, "X":10, "V":5, "I":1}

    # main body
    for i in range(len(s)-1) :
        if roman[s[i]] < roman[s[i+1]] :
            out -= roman[s[i]]
        else :
            out += roman[s[i]]
    return out + roman[s[-1]]