Solution: Roman to Integer
Tags: algorithms, javascript, java, python
Published: 2021-02-20 09:52:00

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/roman-to-integer/discuss/1074149).*

---

#### [Leetcode Problem #13 (*Easy*): Roman to Integer](https://leetcode.com/problems/roman-to-integer/)

---

#### *Description:*
</br>
(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.
>
Symbol|Value
|---|---|
I|1
V|5
X|10
L|50
C|100
D|500
M|1000
>
For example, `2` is written as `II` in Roman numeral, just two one's added together. `12` is written as `XII`, which is simply `X + II`. The number `27` 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.

---

#### *Examples:*
>
Example 1:||
|---:|---|
Input:|s = "III"
Output:|3
>
Example 2:||
|---:|---|
Input:|s = "IV"
Output:|4
>
Example 3:||
|---:|---|
Input:|s = "IX"
Output:|9
>
Example 4:||
|---:|---|
Input:|s = "LVIII"
Output:|58
Explanation:|L = 50, V= 5, III = 3.
>
Example 5:||
|---:|---|
Input:|s = "MCMXCIV"
Output:|1994
Explanation:|M = 1000, CM = 900, XC = 90 and IV = 4.

---

#### *Constraints:*
>
 - `1 <= s.length <= 15`
 - `s` contains only the characters `('I', 'V', 'X', 'L', 'C', 'D', 'M')`.
 - It is guaranteed that `s` is a valid roman numeral in the range `[1, 3999]`.

---

#### *Idea:*
</br>
(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The only really tricky thing about counting in roman numerals is when a numeral is used as a subtractive value rather than an additive value. In **"IV"** for example, the value of **"I"**, **1**, is subtracted from the value of **"V"**, **5**. Otherwise, you're simply just adding the values of all the numerals.

The one thing we should realize about the subtractive numerals is that they're identifiable because they appear *before* a larger number. This means that the easier way to iterate through roman numerals is from right to left, to aid in the identifying process.

So then the easy thing to do here would be to iterate backwards through **S**, look up the value for each letter, and then add it to our answer (**ans**). If we come across a letter value that's smaller than the largest one seen so far, it should be subtracted rather than added.

The standard approach would be to use a separate variable to keep track of the highest value seen, but there's an easier trick here. Since numbers generally increase in a roman numeral notation from right to left, any subtractive number must also be smaller than our current **ans**.

So we can avoid the need for an extra variable here. We do run into the case of repeated numerals causing an issue (ie, **"III"**), but we can clear that by multiplying **num** by either **3** or **4** before comparing it to **ans**, since the numerals jump in value by increments of at least **5x**. (_Note: **2** is too small of a multiplier due to the possibility of a triple character followed by another, ie: **"XXXI"** where **2 * 10 < 21**_)

Once we know how to properly identify a subtractive numeral, it's a simple matter to just iterate backwards through **S** to find and **return** the **ans**.

---

#### *Implementation:*

Javascript and Python both operate with objects / disctionaries quite quickly, so we'll use a lookup table for roman numeral values.

Java and C++ don't deal with objects as well, so we'll use a switch case to function much the same way.

---

#### *Javascript Code:*
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
const roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}

var romanToInt = function(S) {
    let ans = 0
    for (let i = S.length-1; ~i; i--) {
        let num = roman[S.charAt(i)]
        if (4 * num < ans) ans -= num
        else ans += num
    }
    return ans
};
```

---

#### *Python Code:*
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}

class Solution:
    def romanToInt(self, S: str) -> int:
        ans = 0
        for i in range(len(S)-1,-1,-1):
            num = roman[S[i]]
            if 4 * num < ans: ans -= num
            else: ans += num
        return ans
```

---

#### *Java Code:*
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int romanToInt(String S) {
        int ans = 0, num = 0;
        for (int i = S.length()-1; i >= 0; i--) {
            switch(S.charAt(i)) {
                case 'I': num = 1; break;
                case 'V': num = 5; break;
                case 'X': num = 10; break;
                case 'L': num = 50; break;
                case 'C': num = 100; break;
                case 'D': num = 500; break;
                case 'M': num = 1000; break;
            }
            if (4 * num < ans) ans -= num;
            else ans += num;
        }
        return ans;
    }
}
```

---

#### *C++ Code:*
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int romanToInt(string S) {
        int ans = 0, num = 0;
        for (int i = S.size()-1; ~i; i--) {
            switch(S[i]) {
                case 'I': num = 1; break;
                case 'V': num = 5; break;
                case 'X': num = 10; break;
                case 'L': num = 50; break;
                case 'C': num = 100; break;
                case 'D': num = 500; break;
                case 'M': num = 1000; break;
            }
            if (4 * num < ans) ans -= num;
            else ans += num;
        }
        return ans;        
    }
};
```