Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1 2 3 4 5 6 7 8

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000

I can be placed before V (5) and X (10) to make IV (4) and IX (9).

X can be placed before L (50) and C (100) to make XL (40) and XC (90).

C can be placed before D (500) and M (1000) to make CD (400) and CM (900).

Roman to Integer

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13

Input: "III" Output: 3

Input: "IV" Output: 4

Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.

Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90andIV=4.

First, we need a function that receives a character and returns the corresponded value.

1 2 3 4 5 6 7 8 9 10

privateintgetVal(char ch) { if (ch == 'I') return1; if (ch == 'V') return5; if (ch == 'X') return10; if (ch == 'L') return50; if (ch == 'C') return100; if (ch == 'D') return500; if (ch == 'M') return1000; thrownewIllegalArgumentException("Unsupported Character"); }

The idea is very elegant. Each time we look ahead one element and compare the current element curr with the next element next.

curr < next: Combination, eg. IX.

curr >= next: Single Symbol, eg. III.

The way of handling symbols like IX is very clever. We first deduct the value of the first symbol and then add the value of the second symbol. For this example IX, we first deduct I(1) and then add X(5), which turns out to be 4.

Here is the code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

publicintromanToInt(String s) { intn= s.length(); intresult=0; if (n == 0) return result; for (inti=0; i < n - 1; ++i) { intcurr= getVal(s.charAt(i)); intnext= getVal(s.charAt(i + 1)); if (curr < next) { result -= curr; } else { result += curr; } } return result + getVal(s.charAt(n - 1)); }

Actually, we can check the index before assigning a value to next. With this check, the code becomes more elegant and succinct.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

publicintromanToInt(String s) { intn= s.length(); intresult=0; for (inti=0; i < n; ++i) { intcurr= getVal(s.charAt(i)); intnext= (i + 1 < n) ? getVal(s.charAt(i + 1)) : Integer.MIN_VALUE; if (curr < next) { result -= curr; } else { result += curr; } } return result; }

Time: $O(N)$ Space: $O(1)$

Integer to Roman

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13

Input: 3 Output: "III"

Input: 4 Output: "IV"

Input: 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.

Input: 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90andIV=4.

The idea is to check all possible bases from largest to smallest. For example, we should use M(1000) to reduce 1994 to 994, and then CM(900) and so on.