Roman To Integer - Leetcode Solution

Problem Statement:

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 one's 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.

Example 1:

Input: s = "III" Output: 3

Example 2:

Input: s = "IV" Output: 4

Example 3:

Input: s = "IX" Output: 9

Example 4:

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

Example 5:

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].

Approach:

To solve this problem, we can use the following steps:

1. Create a dictionary to store the integer values of each roman numeral symbol.

2. Initialize a variable 'number' to zero.

3. Traverse through the roman numeral string and check the current symbol and the next symbol to determine if it is a subtrahend.

4. If it is a subtrahend, subtract the current symbol value from the next symbol value and add it to the 'number' variable.

5. If it is not a subtrahend, simply add the current symbol value to the 'number' variable.

6. Return the 'number' variable.

Code:

Here is the Python 3 code implementing the above approach:

class Solution: def romanToInt(self, s: str) -> int: # create a dictionary to store the integer values of each roman numeral symbol roman_dict = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

    # initialize a variable 'number' to zero
    number = 0
    
    # traverse through the roman numeral string
    for i in range(len(s)):
        # check the current symbol and the next symbol to determine if it is a subtrahend
        if i < len(s) - 1 and roman_dict[s[i]] < roman_dict[s[i+1]]:
            # subtract the current symbol value from the next symbol value and add it to the 'number' variable
            number -= roman_dict[s[i]]
        else:
            # simply add the current symbol value to the 'number' variable
            number += roman_dict[s[i]]
    
    # return the 'number' variable
    return number

Time Complexity Analysis:

The time complexity of the above code is O(n) where n is the length of the input roman numeral string.

This is because we traverse through the string once and perform constant time operations for each symbol.

Hence, the time complexity of the algorithm is linear in the length of the input string.

Space Complexity Analysis:

The space complexity of the above code is O(1) because we use a dictionary to store the integer values of each Roman numeral symbol.

The size of the dictionary is constant, and does not depend on the length of the input string.

Therefore, the space complexity of the algorithm is constant.

1