LESSON 558 OF 635 · MATH

Roman to Integer in Python

Practice O(n)

You get a string s that holds a Roman numeral. Return the number it stands for.

Roman numerals use seven letters. Each letter has a value:

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

Usually the letters go from larger values to smaller ones. Then the number is the sum of their values.

Six pairs break that order. In each one, a smaller letter comes just before a larger one. That smaller letter is subtracted:

IV = 4     IX = 9
XL = 40    XC = 90
CD = 400   CM = 900

Example 1:

Input: s = "XXXI"
Output: 31
Explanation: No letter comes before a larger one.
So you add them all: 10 + 10 + 10 + 1 = 31.

Example 2:

Input: s = "XIV"
Output: 14
Explanation: X is 10.
Then comes the pair IV, which is 4.
In total, 10 + 4 = 14.

Example 3:

Input: s = "DCCCXLIX"
Output: 849
Explanation: D is 500, and CCC is 300.
XL is 40, and IX is 9.
In total, 500 + 300 + 40 + 9 = 849.

Constraints:

s has 1 to 15 letters.
Each letter is one of the seven above.
The numeral in s is always valid.
Its value is from 1 to 3,999.

Note:

Your solution should run in O(n) time, where n is the length of s.

Look at each letter together with the letter after it. When the next letter has a larger value, this letter is the first half of a pair like IV.

Subtract a letter's value when the next letter is larger. Otherwise, and for the last letter, add it. In XIV that gives 10 - 1 + 5 = 14.

Each letter takes one lookup in a map of 7 letters and one addition or subtraction: O(n) time.
The map always has 7 entries, so the extra space is O(1).

STEP 1 OF 7

Guided

Ctrl + Enter to check

Roman to Integer in Python

Roman To Integer in Python