LeetCode 13. Roman to Integer

Description

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, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

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

Example 5:

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

Explanation

The problem is about writing a function to convert a Roman number to an Arabic number.

We need to have some basic knowledge about Roman numerals.

Roman numerals, as used today, are based on seven symbols:

Symbol	I	V	X	L	C	D	M
Value	1	5	10	50	100	500	1,000

Numbers are formed by combining symbols and adding the values. Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX), a subtractive notation is used: as in this table:

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

• I placed before V or X indicates one less, so four is IV (one less than five) and nine is IX (one less than ten)
• X placed before L or C indicates ten less, so forty is XL (ten less than fifty) and ninety is XC (ten less than a hundred)
• C placed before D or M indicates a hundred less, so four hundred is CD (a hundred less than five hundred) and nine hundred is CM (a hundred less than a thousand)

First we use a map to store the relationship between 7 basic Roman symbol and their values.

Then we read the input string from right to the left. Whenever we visit one roman symbol, we compare its values with right symbol value. If it is bigger than or equal to the right symbol value, we add the current symbol value to the result. Otherwise, we minus the current symbol value from the result.

Java Solution

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, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3
Example 2:

Input: "IV"
Output: 4
Example 3:

Input: "IX"
Output: 9
Example 4:

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

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

Python Solution

class Solution:
    def romanToInt(self, s: str) -> int:
        
        romans = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        
        result = 0
        
        i = len(s) - 1
        while i > -1:
            char = s[i]
            if (char == 'V' and i != 0 and s[i - 1] == 'I'):
                result += 4
                i -= 2
            elif (char == 'X' and i != 0 and s[i - 1] == 'I'):
                result += 9
                i -= 2
            elif (char == 'L' and i != 0 and s[i - 1] == 'X'):
                result += 40
                i -= 2       
            elif (char == 'C' and i != 0 and s[i - 1] == 'X'):
                result += 90
                i -= 2       
            elif (char == 'D' and i != 0 and s[i - 1] == 'C'):
                result += 400
                i -= 2     
            elif (char == 'M' and i != 0 and s[i - 1] == 'C'):
                result += 900
                i -= 2                     
            else:                
                result += romans[char]
                i -= 1
        
        return result

• Time complexity: O(N)
• Space complexity: O(1)