Solving the "Roman to Integer" Problem on LeetCode
Tags: java, coding, programming, productivity
Published: 2023-09-05 09:15:28

**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 ones 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:_

1. I can be placed before V (5) and X (10) to make 4 and 9. 
2. X can be placed before L (50) and C (100) to make 40 and 90. 
3. C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

**Example 1:**

Input: s =`"III"`
Output: `3`
Explanation: `III = 3.
`
**Example 2:**

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

**Example 3:**

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].
```

## Approach:

1. **Create a Hashtable:** First, a Hashtable named Tabl is created to map Roman numeral characters to their corresponding integer values. This mapping is essential for converting each character in the input string to its numerical equivalent.

3. **Initialize Variables:** Two integer variables are initialized:

3. **sum:** This variable will store the cumulative integer value of the Roman numeral string.

4. **prevValue:** This variable keeps track of the previous Roman numeral's value while iterating through the string.Iterate through the String in Reverse: The code uses a for loop to iterate through the input string s in reverse order, starting from the last character and moving towards the first character. This reverse iteration is crucial for handling cases where smaller numerals precede larger ones (e.g., "IV" for 4 or "CM" for 900).

5. **Retrieve the Value of the Current Character:** Inside the loop, the code retrieves the integer value of the current Roman numeral character (ch) using the Hashtable Tabl.get(ch).

6. **Check for Smaller Preceding Numeral:** The code checks whether the current numeral's value (data) is less than the previous numeral's value (prevValue). This check is used to determine whether subtraction is required, as Roman numerals are constructed using both addition and subtraction rules.

7. **Update the sum Variable:** Depending on the comparison result, the code either subtracts the current numeral's value (data) from the sum or adds it to the sum. This step accumulates the overall integer value of the Roman numeral string.
 
8. **Update prevValue:** After processing the current character, the prevValue variable is updated with the current numeral's value to be used in the next iteration.
 
9. **Return the Result:** After processing all characters in the input string, the final integer value (sum) is returned as the result of the conversion.

## Code:

```
import java.util.Hashtable;

class Solution {
    public int romanToInt(String s) {
        Hashtable<Character, Integer> Tabl = new Hashtable<>();
        Tabl.put('I', 1);
        Tabl.put('V', 5);
        Tabl.put('X', 10);
        Tabl.put('L', 50);
        Tabl.put('C', 100);
        Tabl.put('D', 500);
        Tabl.put('M', 1000);

        int sum = 0;
        int prevValue = 0; 

        for (int i = s.length() - 1; i >= 0; i--) {
            char ch = s.charAt(i);
            int data = Tabl.get(ch);
            if (data < prevValue) {
                sum -= data;
            } else {
                sum += data;
            }

            prevValue = data;
        }

        return sum;
    }
}
```

## Explanation: 

_The code uses the Hashtable to efficiently map Roman numeral characters to their integer values. It leverages reverse iteration to handle subtraction cases and accumulates the result in the sum variable. By comparing the current numeral's value with the previous one, it determines whether to add or subtract values, ensuring accurate conversion from Roman numerals to integers._

_This approach is both concise and efficient for solving the problem of converting Roman numerals to integers, and it adheres to the rules and conventions of Roman numeral representation._