Roman to Integer

Problem Statement

Roman numerals are represented using seven unique symbols: I, V, X, L, C, D, and M, with each symbol corresponding to specific integer values. These numerals are combined and occasionally subtracted following specific rules to represent numbers. For example, the numeral for '2' is represented as "II", signifying a simple addition of two ones. However, Roman numeral rules adjust for specific instances, such as four being written as "IV" instead of "IIII", which uses subtraction to modify the representation (1 before 5 signifies a subtraction of one from five).

The numerals typically appear from largest to smallest from left to right unless implementing the subtraction rule. The task is to interpret these numeral strings and convert them into their corresponding integer values. The challenge lies in correctly handling both the direct additive relationships as well as the specific subtractive rules embedded within the numeral format.

Examples

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 and Intuition

To convert a Roman numeral into its integer form, we should consider two main tasks:

1. Understand each Roman numeral symbol and its corresponding value.
2. Recognize when subtraction is used instead of addition.

Process Overview:

1. Create a map of Roman numerals to their respective values:
   • I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
2. Traverse the string from left to right and convert each symbol to its value.
3. To handle the subtraction cases, compare each symbol with the next one:
   • If a symbol represents a smaller number than the one that follows (e.g., I before V), subtract the smaller value from the sum instead of adding.
   • Otherwise, simply add the value of the symbol to the total sum.

Detailed Steps:

1. Initialize a total sum as 0.
2. Iterate over the string of Roman numerals until the second-to-last character.
   • For each character, check if it and the next character form a subtraction pair (like IV or IX).
   • If a subtraction condition is met, subtract the current value from the total.
   • If not, add the current character's value.
3. Add the value of the last character to the total (since there's no next character to check for a subtraction condition).

By following these steps, you can correctly interpret any valid Roman numeral string within the provided constraints of length and characters, ensuring an accurate translation to its integer equivalent.

Solutions

class Solution {
public:
    static unordered_map<char, int> romanValues;
    int convertRomanToInt(string roman) {
        char previousChar = roman[roman.size() - 1];
        int previousValue = romanValues[previousChar];
        int result = previousValue;
    
        for (int index = roman.size() - 2; index >= 0; index--) {
            char currentChar = roman[index];
            int currentValue = romanValues[currentChar];
            if (currentValue < previousValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
            previousValue = currentValue;
        }
        return result;
    }
};
    
unordered_map<char, int> Solution::romanValues = {
    {'M', 1000}, {'D', 500}, {'C', 100}, {'L', 50},
    {'X', 10},   {'V', 5},   {'I', 1}};