LeetCode 13: Roman to Integer Explained

The problem "Roman to Integer" is a classic LeetCode challenge that tests your understanding of Roman numerals. In this post, I will provide a step-by-step explanation of how to solve this problem in Python.

Problem Overview

Roman numerals are a system of numerical notation that uses letters to represent numbers. The letters I, V, X, L, C, D, and M represent the numbers 1, 5, 10, 50, 100, 500, and 1000, respectively.

To convert a Roman numeral to an integer, you simply add up the values of the letters. However, there are a few exceptions to this rule. For example, the Roman numeral IV represents the number 4, not 6. This is because when a smaller value letter is placed before a larger value letter, it is subtracted from the larger value.

Solution

Here is a Python function that converts a Roman numeral to an integer:

def roman_to_int(s):
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    n = len(s)
    result = 0
    i = 0
    while i < n:
        current_value = roman_map[s[i]]
        next_value = roman_map[s[i+1]] if i+1 < n else 0
        if current_value < next_value:
            result += next_value - current_value
            i += 2
        else:
            result += current_value
            i += 1
    return result

This function works by iterating over the Roman numeral string and checking if the current value is less than the next value. If it is, then the current value is subtracted from the next value. Otherwise, the current value is added to the result.

Test Cases

>>> roman_to_int("III")
3
>>> roman_to_int("IV")
4
>>> roman_to_int("IX")
9
>>> roman_to_int("LVIII")
58
>>> roman_to_int("MCMXCIV")
1994

Conclusion

In this post, I have provided a step-by-step explanation of how to solve the LeetCode problem "Roman to Integer" in Python. I hope you found this post helpful. If you have any questions, please leave a comment below.