LeetCode 13 - Roman to Integer

Question:

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.

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.

Answer:

The solution aims to convert a Roman numeral representation into its corresponding integer value. It utilizes the properties of Roman numerals, such as the rules of addition.

Approach:

Iterate through each character of the Roman numeral string.
Use a switch statement to handle each character case ('I', 'V', 'X', 'L', 'C', 'D', 'M').
Based on the current character and the previous character, determine which value should be added.
Update the total value accordingly and keep track of the previous character for future comparisons.
Finally, return the calculated integer value.

Explanation of Logic:

The prev variable is used to keep track of the previous character's value, initialized to 0.
The loop iterates over each character of the input Roman numeral string.
For each character
- If the character is I, add 1 to the total value and update prev to 1.
- If the character is V
  - If the previous character was I (value = 1), it means we encountered 'IV', so add 3 to the total value (1 + 3 = 4).
  - If the previous character was not 'I', add 5 to the total value and update prev to 5.
- Similar logic is applied for X, L, C, D, and M cases, considering their respective values and the previous character.

After processing all characters, the total value is returned.

Time Complexity:

The time complexity is O(n), where n is the length of the input Roman numeral string. The algorithm iterates through each character once.

Space Complexity:

The space complexity is O(1) as the space usage remains constant irrespective of the input size.

Code:

class Solution:
    def romanToInt(self, s: str) -> int:
        value = 0
        prev = 0
        for ch in s:
            if ch == 'I':
                value += 1
                prev = 1
            elif ch == 'V':
                value += 3 if prev == 1 else 5
                prev = 5
            elif ch == 'X':
                value += 8 if prev == 1 else 10
                prev = 10
            elif ch == 'L':
                value += 30 if prev == 10 else 50
                prev = 50
            elif ch == 'C':
                value += 80 if prev == 10 else 100
                prev = 100
            elif ch == 'D':
                value += 300 if prev == 100 else 500
                prev = 500
            elif ch == 'M':
                value += 800 if prev == 100 else 1000
                prev = 1000
        return value