Leetcode – Roman to Integer

Spread the love

Roman numerals are a numeral system that originated in ancient Rome and remained the usual way of writing numbers throughout Europe well into the Late Middle Ages. They are represented by combinations of the letters I, V, X, L, C, D, and M. Understanding and converting Roman numerals is a common problem in algorithmic challenges. One such problem is presented in LeetCode, a popular online platform for programming interview preparation.

This article is dedicated to the “Roman to Integer” problem from LeetCode, aiming to provide an in-depth exploration of the problem and different strategies to solve it using Python.

Problem Statement

LeetCode Problem #13: Roman to Integer

Given a roman numeral, convert it to an integer.

Example

Input: s = "III"
Output: 3

The problem seems straightforward: we are asked to convert a Roman numeral into an integer. However, Roman numerals follow certain rules that make this task non-trivial.

Understanding Roman Numerals

Before we delve into the coding aspect, it’s important to have a basic understanding of Roman numerals. Here are the primary symbols and their integer equivalents:

I => 1
V => 5
X => 10
L => 50
C => 100
D => 500
M => 1000

Roman numerals are written by combining the letters and adding their values. But there’s a special rule: when smaller numbers appear before larger ones, we subtract the smaller number. For example, IV is not IIII (4); it’s 5 – 1, which equals 4.

Approach 1: Naive Approach

The most straightforward way to solve this problem is to iterate over the string, convert each character to its integer equivalent, and add up the numbers. However, we need to take care of the subtraction rule.

Here is a Python function that implements this approach:

def romanToInt(s: str) -> int:
    roman_to_int = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev = 0
    for c in reversed(s):
        current = roman_to_int[c]
        if prev > current:
            total -= current
        else:
            total += current
        prev = current
    return total

In this function, we create a dictionary to map Roman numerals to their integer equivalents. We then iterate over the string in reverse order. For each character, we subtract its value if it is less than the previous character’s value (which means we’re in a situation like IV or IX), and add it otherwise.

While this solution is relatively straightforward, it has some inefficiencies. For example, it iterates over the entire string, and it checks each character against the subtraction rule, even though this rule only applies to six cases (IV, IX, XL, XC, CD, and CM). Can we make it more efficient?

Approach 2: Optimized Approach

In this approach, we will handle the six special cases explicitly. This reduces the number of comparisons we need to make.

Here is a Python function that implements this optimized approach:

def romanToInt(s: str) -> int:
    roman_to_int = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    i = 0
    while i < len(s):
        # If this is a subtraction case.
        if i < len(s) - 1 and roman_to_int[s[i]] < roman_to_int[s[i+1]]:
            total += roman_to_int[s[i+1]] - roman_to_int[s[i]]
            i += 2
        # Else this is a normal case.
        else:
            total += roman_to_int[s[i]]
            i += 1
    return total

This function works similarly to the first one, but it checks each pair of characters for the subtraction rule before adding their values to the total. If the subtraction rule applies, it adds the difference of the two numbers and skips the next character.

This function is more efficient than the first one because it handles the special cases explicitly, reducing the number of comparisons we need to make.

Conclusion

The “Roman to Integer” problem is an excellent example of a problem where understanding the domain (in this case, Roman numerals) is as important as understanding the algorithms and data structures needed to solve it. The Python solutions we discussed demonstrate different ways to approach the problem and provide valuable insights into problem-solving strategies.

While the first solution is simple and intuitive, the second one is more efficient, demonstrating the importance of optimizing your code after getting a working solution.

Leave a Reply