Problem statement

Roman numerals are written with the symbols I, V, X, L, C, D and M, worth 1, 5, 10, 50, 100, 500 and 1000.

Numbers are normally written largest to smallest and added up, but six subtractive pairs exist: IV (4), IX (9), XL (40), XC (90), CD (400) and CM (900).

Given a valid roman numeral s, convert it to an integer.

Example 1

Input: s = "III"
Output: 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, IV = 4.

Constraints

• 1 <= s.length <= 15
• s is a valid roman numeral in the range [1, 3999].

Hints for Roman to Integer

1. Hint 1

   Scan left to right and look one symbol ahead.

2. Hint 2

   A symbol worth less than the one after it is being subtracted; otherwise it is added.

3. Hint 3

   That single rule covers all six subtractive pairs without listing them.

How to solve Roman to Integer

Scan left to right and compare each symbol with the one after it: a value smaller than its successor is being subtracted, everything else is added. That one rule covers all six subtractive pairs.

Approach

1. Map each symbol to its value.
2. For each index i, if i + 1 exists and val[s[i]] < val[s[i+1]], subtract val[s[i]]; otherwise add it.
3. Return the total.

Why it works

In a valid numeral the only place a smaller symbol precedes a larger one is inside a subtractive pair (IV, IX, XL, XC, CD, CM), and in each pair the pair's value is larger - smaller. Subtracting the first symbol and later adding the second yields exactly that.

Complexity

• Time — O(len)
• Space — O(1)

Pitfalls

• Hard-coding the six pairs with a two-character lookahead also works but is easy to typo; the comparison rule is shorter and identical in effect.
• The last symbol has no successor and is always added.

Reference solution

Python

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

Java

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

C++

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

JavaScript

var romanToInt = function(s) {
    const val = { 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++) {
        if (i + 1 < s.length && val[s[i]] < val[s[i + 1]]) total -= val[s[i]];
        else total += val[s[i]];
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy