Roman to Integer

easy string hash map

Problem

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.

Inputs = "MCMXLIV"

Output1944

M (1000) + CM (900) + XL (40) + IV (4) = 1944.

s (uppercase Roman numeral)

def roman_to_int(s):
    v = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}
    total = 0
    for i, ch in enumerate(s):
        cur = v[ch]
        nxt = v[s[i + 1]] if i + 1 < len(s) else 0
        total += -cur if cur < nxt else cur
    return total

function romanToInt(s) {
  const v = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
  let total = 0;
  for (let i = 0; i < s.length; i++) {
    const cur = v[s[i]];
    const next = i + 1 < s.length ? v[s[i + 1]] : 0;
    total += (cur < next) ? -cur : cur;
  }
  return total;
}

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> v = Map.of(
            'I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000);
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = v.get(s.charAt(i));
            int next = (i + 1 < s.length()) ? v.get(s.charAt(i + 1)) : 0;
            total += (cur < next) ? -cur : cur;
        }
        return total;
    }
}

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

Explanation

Roman numerals are usually just added up, but a few special pairs like IV or CM mean "subtract". The key observation: a symbol is subtracted exactly when a larger symbol comes right after it.

We store each symbol's value in a lookup map v (I=1, V=5, X=10, ...). Then we scan left to right. For each character we compare its value cur with the value of the next character nxt.

If cur < nxt, this symbol is part of a subtractive pair, so we add -cur; otherwise we add cur normally. The last character has nothing after it, so we treat its "next" value as 0 and always add it.

Example: s = "MCMXLIV". M(1000) is added. C(100) is before M(1000), so subtract → -100; then M adds +1000. X(10) before L(50) subtracts -10; L adds +50. I(1) before V(5) subtracts -1; V adds +5. Total: 1000 - 100 + 1000 - 10 + 50 - 1 + 5 = 1944.

One pass over the string with constant-size lookups makes this linear and simple.

Time: O(n) Space: O(1)