Mastering LeetCode: Converting Roman to Integer

Introduction to Roman Numerals Conversion

Roman numerals, a numeral system originating in ancient Rome, are used in various applications even today, from clock faces to movie release years. However, translating them into integers that modern computers can understand poses an interesting challenge (LeetCode 13).

Roman numerals are composed of seven symbols each representing a fixed integer value. Numbers are generally formed by combining these symbols, following specific rules not only for addition but also for subtraction, making the system slightly complex but intriguing for algorithmic implementation.

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       ValueI             1V             5X             10L             50C             100D             500M             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 27is 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: 3Explanation: III = 3.

Example 2:

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

Example 3:

Input: s = "MCMXCIV"Output: 1994Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Analyzing Different Approaches

To solve the problem of converting Roman numerals to integers, one can consider multiple approaches:

1. Sequential Parsing: Start from the left, read each symbol, and add its value to the total. When a symbol smaller than its successor is found, subtract its value instead of adding it. This approach reflects the most direct interpretation of the rules.

2. Replace and Sum: Convert subtractive combinations (like IV or IX) into their additive equivalents (IIII or VIIII) before summing. This simplifies parsing but requires preprocessing the input string.

3. Mapping and Lookup: Use a dictionary to map each Roman numeral symbol to its value, enabling quick conversions and handling exceptions for subtractive cases as special conditions within the loop.

Solution and Complexity Analysis

The optimal solution for both readability and performance is the Sequential Parsing approach. This method involves iterating over the string of Roman numerals, checking the value of the current symbol against the next symbol. If the current symbol's value is less than the next one, it indicates a subtractive combination, and we subtract rather than add the value.

Complexity Analysis

• Time Complexity: O(n), where n is the length of the Roman numeral string. Each symbol is processed once.

• Space Complexity: O(1), as the extra space required is minimal and does not depend on the input size.

Solutions

Python Solution

def romanToInt(s: str) -> int:    translations = {        "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000    }    total = 0    prev_value = 0    for char in reversed(s):        value = translations[char]        if value >= prev_value:            total += value  # Add the value if it's not a subtractive combination        else:            total -= value  # Subtract the value if it's a subtractive combination        prev_value = value    return total

TypeScript Solution

function romanToInt(s: string): number {    const translations: { [key: string]: number } = {        "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000    };    let total = 0;    let prevValue = 0;    for (let i = s.length - 1; i >= 0; i--) {        const value = translations[s.charAt(i)];        if (value >= prevValue) {            total += value;        } else {            total -= value;        }        prevValue = value;    }    return total;}

Java Solution

public int romanToInt(String s) {    int[] values = new int[s.length()];    for (int i = 0; i < s.length(); i++) {        values[i] = switch (s.charAt(i)) {            case 'I' -> 1;            case 'V' -> 5;            case 'X' -> 10;            case 'L' -> 50;            case 'C' -> 100;            case 'D' -> 500;            case 'M' -> 1000;            default -> 0;        };    }    int total = 0;    for (int i = 0; i < values.length - 1; i++) {        if (values[i] < values[i + 1])            total -= values[i];        else            total += values[i];    }    total += values[values.length - 1];    return total;}

Python Solution #2

Finally, if you're feeling really sneaky, you can use replaces.

def romanToInt(self, s: str) -> int:        translations = {            "I": 1,            "V": 5,            "X": 10,            "L": 50,            "C": 100,            "D": 500,            "M": 1000        }        intNum = 0        iSubtractions = s.replace("IV", "IIII").replace("IX", "VIIII")        xSubtractions = iSubtractions.replace("XL", "XXXX").replace("XC", "LXXXX")        cSubtractions = xSubtractions.replace("CD", "CCCC").replace("CM", "DCCCC")        for char in cSubtractions:            intNum += translations[char]        return intNum

Conclusion

Understanding and implementing the conversion of Roman numerals to integers exemplifies a basic yet critical algorithmic problem-solving skill. Each solution in Python, TypeScript, and Java highlighted here not only serves the functional requirement but also helps in grasping fundamental programming concepts like arrays, loops, and conditional logic.

For anyone preparing for software engineering interviews, mastering such problems is invaluable, enhancing both your problem-solving skills and your readiness for technical challenges.

Feel free to analyze, run, and modify the provided solutions as per your learning and testing needs. Happy coding!