Roman to Integer

Problem

Convert a Roman numeral string to its integer value.

Input:  s = "MCMXCIV"
Output: 1994

Python Solution

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

C++ Solution

int romanToInt(string s) {
    unordered_map<char, int> values = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && values[s[i]] < values[s[i + 1]]) {
            total -= values[s[i]];
        } else {
            total += values[s[i]];
        }
    }
    return total;
}

Java Solution

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

Complexity

Time: O(n) — one pass through the string, with an O(1) lookup per character. Space: O(1) — the value map has a fixed size of seven symbols.