Converting Roman Numerals to Decimal

The problem, simply

Romans wrote numbers with letters: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. You get a valid Roman numeral as a string. Give back its value as a normal number.

Usually you add the letters up: XVI is 10 + 5 + 1 = 16. But a smaller letter right before a bigger one means "take this away": IV is 5 - 1 = 4, and XC is 100 - 10 = 90.

A story to remember it

Picture it

Examples

Way 1: the simple way

Learn the six special pairs by heart: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900. Walk the string. If the next two letters form a special pair, add the pair's value and jump two letters. Otherwise add one letter's value and step one.

import java.util.*;

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> one = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
        Map<String, Integer> pair = Map.of("IV", 4, "IX", 9, "XL", 40, "XC", 90, "CD", 400, "CM", 900);
        int total = 0, i = 0;
        while (i < s.length()) {
            if (i + 1 < s.length() && pair.containsKey(s.substring(i, i + 2))) {
                total += pair.get(s.substring(i, i + 2));   // a special pair
                i += 2;
            } else {
                total += one.get(s.charAt(i));              // a single letter
                i += 1;
            }
        }
        return total;
    }
}

How long it takes: each letter is looked at once or twice, O(n). Extra room: two small fixed tables, O(1). It works, but you must remember the exact list of pairs, and it makes small new strings with substring.

Way 2: the clever way

You do not need the list of pairs. The rule hiding in all six pairs is the same: a letter smaller than the letter after it is taken away.

1. For each letter, find its value cur and the value of the next letter next (use 0 after the last letter).
2. If cur < next, subtract cur. Otherwise add cur.

class Solution {
    private int value(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default:  return 1000;   // 'M'
        }
    }

    public int romanToInt(String s) {
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = value(s.charAt(i));
            int next = (i + 1 < s.length()) ? value(s.charAt(i + 1)) : 0;
            if (cur < next) total -= cur;   // ten to six: take it away
            else total += cur;              // normal: add it
        }
        return total;
    }
}

How long it takes: one walk, O(n). Extra room: O(1). Both ways have the same speed. This one wins because the code is shorter and there is no list to get wrong.

Watch out for

• The last letter has no neighbor. Treat the missing neighbor as 0, or read past the end and crash.
• Equal letters are added: XX is 20, not 0. The test is cur < next, not cur <= next.
• The input is promised valid. If not, strings like IIV or VX would need extra checks.

What interviewers ask next

• Can you go right to left instead? Yes. Keep the biggest value seen so far from the right. If the current letter is smaller than that, subtract it, otherwise add it and update the biggest.
• Turn a number into Roman letters? Greedy: list the 13 values from big to small, 1000, 900, 500, 400, ..., 4, 1, with their letters. Take the biggest that fits as many times as it fits, then move to the next.
• How would you check that a Roman numeral is valid? Only I, X, C may be taken away, only from the next two bigger letters (I from V and X, X from L and C, C from D and M), and no letter repeats more than three times in a row.
• Why stop at 3999? Normal Roman letters have nothing bigger than M, and M may repeat only three times.

Remember this

Grown-up words: peeking right is a one character lookahead, the value table is a lookup table, and "ten to six" letters are the subtractive notation of Roman numerals.