Roman numerals are represented by seven different symbols: `I`

, `V`

, `X`

, `L`

, `C`

, `D`

and `M`

.

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

For example, two is written as `II`

in Roman numeral, just two one’s added together. Twelve is written as, `XII`

, which is simply `X`

+ `II`

. The number twenty-seven is written as `XXVII`

, which is `XX`

+ `V`

+ `II`

. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`

. Instead, the number four is written as `IV`

. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`

. There are six instances where subtraction is used:

`I`

can be placed before`V`

(5) and`X`

(10) to make 4 and 9.`X`

can be placed before`L`

(50) and`C`

(100) to make 40 and 90.`C`

can be placed before`D`

(500) and`M`

(1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:Input: "III" Output: 3Example 2:Input: "IV" Output: 4Example 3:Input: "IX" Output: 9Example 4:Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.

Given that the representation for `3`

is `III`

, it could seem natural that the representation for `15`

is `VVV`

, because that would be `5+5+5`

. However, it’s actually `XV`

, which is `10+5`

. How are you even supposed to know which is correct? **The trick is to use the “biggest” symbols you can**. Because `X`

is bigger than `V`

, we should use an `X`

first and then make up the remainder with a single `V`

, giving `XV`

.

**A few more examples**

If you’re not very familiar with Roman Numerals, work through these examples and then have another go at writing your own algorithm before reading the rest of this solution article.

**What is CXVII as an integer?**

Recall that `C = 100`

, `X = 10`

, `V = 5`

, and `I = 1`

. Because the symbols are ordered from most significant to least, we can simply add the symbols, i.e. `C + X + V + I + I = 100 + 10 + 5 + 1 + 1 = 117`

.

**What is DXCI as an integer?**

Recall that `D = 500`

.

Now, notice that this time the symbols are *not* ordered from most significant to least—the `X`

and `C`

are out of numeric order. Because of this, we subtract the value of `X`

(`10`

) from the value of `C`

(`100`

) to get `90`

.

So, going from left to right, we have `D + (C - X) + I = 500 + 90 + 1 = 591`

.

**What is CMXCIV as an integer?**

Recall that `M = 1000`

.

The symbols barely look sorted at all here—from left-to-right we have `100, 1000, 10, 100, 1, 5`

. Do not panic though, we just need to look for each occurrence of a smaller symbols *preceding* a bigger symbol. The first, third, and fifth symbols are all smaller than their next symbol. Therefore they are all going to be subtracted from their next.

- The first two symbols are
`CM`

. This is`M - C = 1000 - 100 = 900`

- The second two symbols are
`XC`

. This is`C - X = 100 - 10 = 90`

. - The final two symbols are
`IV`

. This is`V - I = 5 - 1 = 4`

.

Like we did above, we add these together. `(M - C) + (C - X) + (V - I) = 900 + 90 + 4 = 994`

.

**Approach: Left-to-Right Pass**

Let’s hard-code a mapping with the value of each symbol so that we can easily look them up.

private Map<Character, Integer> romanMap = new HashMap<>(){{ put('I',1); put('V',5); put('X',10); put('L',50); put('C',100); put('D',500); put('M',1000); }};

Now, recall that each symbol adds its own value, *except for* when a *smaller valued symbol* is *before* a *larger valued symbol*. In those cases, instead of adding both symbols to the total, we need to *subtract the large from the small*, adding that instead. Therefore, the simplest algorithm is to use a pointer to scan through the string, at each step deciding whether to add the current symbol and go forward 1 place, or add the difference of the next 2 symbols and go forward 2 places. Here is this algorithm in pseudocode.

```
total = 0
i = 0
while i < s.length:
if at least 2 symbols remaining AND value of s[i] < value of s[i + 1]:
total = total + (value of s[i + 1]) - (value of s[i])
i = i + 2
else:
total = total + (value of s[i])
i = i + 1
return total
```

Here is an animation of the above algorithm. Recall that the *input is always valid*. This means that we don’t need to worry about being given inputs such as `ICD`

.

**Implementation**

```
class Solution {
private Map<Character, Integer> romanMap = new HashMap<>(){{
put('I',1);
put('V',5);
put('X',10);
put('L',50);
put('C',100);
put('D',500);
put('M',1000);
}};
public int romanToInt(String s) {
int result = 0;
if( s == null || s.isEmpty()){
return result;
}
int i = 0;
int len = s.length();
while( i < len){
int current = romanMap.get(s.charAt(i));
int next = 0;
if( i != (len-1)){
next = romanMap.get(s.charAt(i + 1));
}
if(current >= next){
result = result + current;
i++;
}else{
result = result + (next - current);
i += 2;
}
}
return result;
}
}
```

Categories: Map