011.md

13. Roman to Integer

Difficulty: 🟢 Easy

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, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 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.

Examples:

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

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

Example 3:

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

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Solutions

O(n) solution

Python3

class Solution:
    def romanToInt(self, s: str) -> int:
        single = {
            "M": 1000,
            "D": 500,
            "C": 100,
            "L": 50,
            "X": 10,
            "V": 5,
            "I": 1,
        }
        double = {
            "CM": 900,
            "CD": 400,
            "XC": 90,
            "XL": 40,
            "IX": 9,
            "IV": 4,
        }

        index, number, length = 0, 0, len(s)

        while index < length:
            if index + 1 < length and s[index:index+2] in double:
                number += double[s[index:index+2]]
                index += 2
            else:
                number += single[s[index]]
                index += 1
        return number
            

The given solution solves the problem by performing the following steps:

1. Create two dictionaries: single and double. The single dictionary maps each single Roman numeral to its corresponding integer value, and the double dictionary maps each double Roman numeral (used for subtraction) to its corresponding integer value.
2. Initialize variables index and number to 0. index keeps track of the current index of the Roman numeral string, and number stores the final integer value.
3. Iterate through the Roman numeral string while index is less than the length of the string:
   • Check if the current index plus 1 is within the length of the string and the substring of length 2 starting from the current index is present in the double dictionary.
     • If true, add the corresponding value from the double dictionary to number.
     • Increment index by 2.
   • If the above condition is false, add the value of the single Roman numeral from the single dictionary to number.
     • Increment index by 1.
4. Return the final value of number.

Complexity Analysis

The time complexity of this algorithm is O(n), where n is the length of the Roman numeral string s. We iterate through the string once to convert it into its corresponding integer value.

The space complexity of the algorithm is O(1) because the dictionaries used for conversion have a fixed number of elements.

Summary

The given solution converts a valid Roman numeral s into its corresponding integer value. It uses dictionaries to map the Roman numerals to their integer values and applies the rules for subtraction when necessary. The algorithm has a time complexity of O(n) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.