21. Roman to Integer

Roman numerals are represented by seven symbols: I(1), V(5), X(10), L(50), C(100), D(500), M(1000). Given a roman numeral string, convert it to an integer. Subtraction is used when a smaller value appears before a larger value (e.g., IV = 4, IX = 9).

Input: s = "III"
Output: 3

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

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

Problem Breakdown:

1. Create a mapping of Roman numeral characters to their integer values.

• roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

2. Initialize result to 0. Iterate through the string, checking if the current character represents a subtraction case.

• result = 0
  for i in range(len(s)):

3. If the current value is less than the next value, subtract it (e.g., I before V means 4). Otherwise, add it.

•     if i + 1 < len(s) and roman[s[i]] < roman[s[i+1]]:
          result -= roman[s[i]]
      else:
          result += roman[s[i]]

4. After processing all characters, result holds the integer value.

• return result

Summary:

Map each Roman character to its value. Iterate left to right: if the current value is less than the next, subtract it (subtraction rule); otherwise add it. This handles all cases including IV, IX, XL, XC, CD, CM.

Time and Space Complexity:

Time Complexity: O(n) - single pass through the string.

Space Complexity: O(1) - the mapping has a fixed size of 7 entries.

Python Solution:

def romanToInt(s):
    roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    result = 0
    for i in range(len(s)):
        if i + 1 < len(s) and roman[s[i]] < roman[s[i+1]]:
            result -= roman[s[i]]
        else:
            result += roman[s[i]]
    return result

JavaScript Solution:

var romanToInt = function(s) {
    const roman = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
    let result = 0;
    for (let i = 0; i < s.length; i++) {
        if (i + 1 < s.length && roman[s[i]] < roman[s[i+1]]) {
            result -= roman[s[i]];
        } else {
            result += roman[s[i]];
        }
    }
    return result;
};

Java Solution:

class Solution {
    public int romanToInt(String s) {
        Map roman = Map.of(
            'I', 1, 'V', 5, 'X', 10, 'L', 50,
            'C', 100, 'D', 500, 'M', 1000);
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 < s.length() && roman.get(s.charAt(i)) < roman.get(s.charAt(i+1))) {
                result -= roman.get(s.charAt(i));
            } else {
                result += roman.get(s.charAt(i));
            }
        }
        return result;
    }
}