Roman to Integer easy

Problem Statement

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.

Example 1:

Input: s = "III" Output: 3 Explanation: III = 3.

Example 2:

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

Steps

1. Create a HashMap: Create a HashMap to store the integer values corresponding to each Roman numeral symbol.
2. Iterate through the Roman numeral string: Iterate through the input string from right to left.
3. Handle subtractive cases: If the current value is less than the next value (e.g., "IV," "IX"), subtract the current value from the result; otherwise, add the current value to the result.

Explanation

The key to efficiently solving this problem lies in processing the Roman numeral string from right to left. This allows us to easily handle the subtractive cases. By comparing the current symbol's value with the previous one, we can determine whether to add or subtract. If we were to iterate left-to-right, we'd need additional logic to track potential subtractive pairs, making the solution more complex.

Code

import java.util.HashMap;
import java.util.Map;

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

        int result = 0;
        int prevValue = 0;

        for (int i = s.length() - 1; i >= 0; i--) {
            char currentChar = s.charAt(i);
            int currentValue = romanMap.get(currentChar);

            if (currentValue < prevValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
            prevValue = currentValue;
        }

        return result;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the Roman numeral string. We iterate through the string once.
• Space Complexity: O(1). The HashMap has a constant size, regardless of the input string length.