13. Roman to Integer

Intuition

Roman numerals are a numeral system originating in ancient Rome, composed of seven symbols with fixed values. The system generally follows a rule where larger numerals precede smaller ones, and their values are added. However, specific pairs use subtraction instead, where a smaller numeral precedes a larger one to indicate a value difference (e.g., IV for 4). Understanding these rules helps in converting a Roman numeral to an integer efficiently.

Approach

1. Mapping Creation: Create a mapping of Roman numerals to their respective integer values using a dictionary.
2. Iterate Through the String: Loop through each character in the input Roman numeral string.
3. Check for Subtraction Cases: For each character, check if it forms a subtraction pair with the next character. If it does, subtract the current value from the next value and add the result to the total, then skip the next character.
4. Add Values: If it doesn't form a subtraction pair, simply add the value of the current character to the total.
5. Return Result: Once all characters are processed, return the total value as the integer representation of the Roman numeral.

Complexity

Time Complexity:

O(n), where n is the length of the Roman numeral string. Each character is processed at most twice.

Space Complexity:

O(1), as the space used by the dictionary and the integer result is constant and does not grow with input size.

Code

C++

#include 
#include 
class Solution {
public:
    int romanToInt(std::string s) {
        int result = 0;
        std::unordered_map map = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };
        for (size_t i = 0; i < s.length(); ++i) {
            if (i == s.length() - 1) {
                result += map[s[i]];
                return result;
            }
            if (map[s[i]] >= map[s[i + 1]]) {
                result += map[s[i]];
            } else {
                result += map[s[i + 1]] - map[s[i]];
                ++i;
            }
        }
        return result;
    }
};

Python

class Solution:
    def romanToInt(self, s: str) -> int:
        result = 0
        roman_map = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        i = 0
        while i < len(s):
            if i == len(s) - 1:
                result += roman_map[s[i]]
                return result
            if roman_map[s[i]] >= roman_map[s[i + 1]]:
                result += roman_map[s[i]]
            else:
                result += roman_map[s[i + 1]] - roman_map[s[i]]
                i += 1
            i += 1
        return result

Java

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

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let result = 0;
    const map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    for (let i = 0; i < s.length; i++) {
        if (i === s.length - 1) {
            result += map[s[i]];
            return result;
        };
        if (map[s[i]] >= map[s[i+1]]) {
            result += map[s[i]];
            console.log(result);
        } else {
            result += map[s[i+1]] - map[s[i]];
            i++
        }
    }
    return result;
};