Roman to Integer
Given a Roman numeral, convert it to an integer. The symbols are I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Normally symbols are written from largest to smallest and added; the six subtractive pairs IV, IX, XL, XC, CD and CM mean 4, 9, 40, 90, 400 and 900. The input is a valid numeral from 1 to 3999. This is LeetCode 13.
Example 1
Output: 3
Example 2
Output: 58
Explanation: L = 50, V = 5, III = 3.
Example 3
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.
How to Think About It
Step 1: Usually, add
In "LVIII", every symbol is at least as large as the one after it, so the value is just the sum: 50 + 5 + 1 + 1 + 1 = 58.
Step 2: A smaller symbol before a larger one is subtracted
In "IV", I comes before the larger V, which means 5 - 1. One rule covers all six subtractive pairs: if a symbol is smaller than the next one, subtract it; otherwise add it.
Step 3: Check it on CM
C (100) is smaller than the following M (1000), so it is subtracted: -100 + 1000 = 900, which is what CM means.
Walkthrough
s = "MCMXCIV"
| Symbol | Value | Next symbol's value | Action | Total |
|---|---|---|---|---|
| M | 1000 | 100 | add | 1000 |
| C | 100 | 1000 | subtract | 900 |
| M | 1000 | 10 | add | 1900 |
| X | 10 | 100 | subtract | 1890 |
| C | 100 | 1 | add | 1990 |
| I | 1 | 5 | subtract | 1989 |
| V | 5 | none | add | 1994 |
Java Solution
The last symbol has no next symbol, so it is always added.
public class RomanToInteger {
public static int romanToInt(String s) {
int total = 0;
for (int i = 0; i < s.length(); i++) {
int v = value(s.charAt(i));
if (i + 1 < s.length() && v < value(s.charAt(i + 1))) {
total -= v; // a smaller symbol before a larger one: IV, XC, ...
} else {
total += v;
}
}
return total;
}
private static 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 static void main(String[] args) {
System.out.println(romanToInt("III")); // 3
System.out.println(romanToInt("LVIII")); // 58
System.out.println(romanToInt("MCMXCIV")); // 1994
}
}The original implementation,