https://leetcode.com/problems/roman-to-integer
Given a roman numeral, convert it to an integer.
Input: s = “III” ,
Output: 3
Explanation: III = 3
Example 2:
Input: s = ” LVIII ” ,
Output: 58
Explanation: L = 50, V= 5, III = 3
Understanding Roman Numerals Conversion
Roman numerals use specific symbols to represent numeric values, such as I for 1, V for 5, X for 10, L for 50, C for 100, D for 500, and M for 1000. One of their unique features is the ability to represent subtraction when a smaller symbol is placed before a larger one, as in IV, where I precedes V to indicate 4.
The goal of the algorithm is to efficiently convert a Roman numeral string into its integer equivalent. This is achieved by traversing the string once and applying logic to handle both addition and subtraction scenarios.
Approach to Conversion
The first step in the conversion process is to create a dictionary that maps Roman numeral symbols to their corresponding integer values. This provides a quick and efficient way to look up the value of each symbol during the traversal of the string.
Next, the algorithm processes the Roman numeral string one character at a time. As it traverses the string, it adds the current symbol’s value to a running total. If the current symbol represents a larger value than the previous one, the algorithm adjusts the total by subtracting twice the value of the previous symbol to account for the subtraction rule in Roman numerals.
Subtraction Logic Explained
The subtraction logic in Roman numeral conversion is applied when the current symbol represents a value greater than the previous symbol. In such cases, the algorithm subtracts twice the value of the previous symbol from the total. This adjustment accounts for the subtraction rule, where the smaller symbol preceding a larger one indicates a reduction.
For example, consider the Roman numeral “I X.” The first symbol, “I,” adds 1 to the total, resulting in a total of 1. When the algorithm processes the second symbol, “X,” it recognizes that 10 is greater than 1 (the value of “I”). To apply the subtraction rule, the algorithm adds 10 to the total but subtracts 2 times 1 (the value of “I”). This results in a final total of 9.
Algorithm’s Efficiency
The algorithm is highly efficient in terms of time complexity. It processes the Roman numeral string in a single pass, making its time complexity O(n), where n is the length of the string. This ensures that the conversion is completed quickly, even for longer strings.
In terms of space complexity, the algorithm requires minimal additional memory. The primary storage includes the dictionary for symbol-to-value mappings and a few variables for calculations, resulting in a constant space complexity of O(1). This efficiency makes the solution both fast and memory-efficient.
Example Walkthrough
Let’s walk through the algorithm using the Roman numeral “MCMXCIV” as an example. The process begins by adding the value of the first symbol, “M,” which is 1000. This sets the initial total to 1000.
Next, the algorithm encounters “C,” which has a value of 100. Since “C” is smaller than the following “M” (1000), it is subtracted from the total. To apply this, the algorithm first adds the next “M” (1000) but subtracts twice the value of “C” (2 × 100), effectively adding 1000 – 200 to the total.
The algorithm then processes “X,” adding its value of 10 to the total. When it reaches “I,” it recognizes that the next symbol, “V,” is larger. It subtracts the value of “I” (1) from “V” (5) and adds the difference. After all these steps, the final total is 1994.
Solution
def roman_to_int(s):
# Dictionary to map Roman numerals to integers
roman_to_int_map = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
# Initialize the integer result
total = 0
# Length of the Roman numeral string
n = len(s)
for i in range(n):
# Get the value of the current symbol
current_value = roman_to_int_map[s[i]]
# If the current value is greater than the previous value, subtract twice the previous value
if i > 0 and current_value > roman_to_int_map[s[i - 1]]:
total += current_value - 2 * roman_to_int_map[s[i - 1]]
else:
total += current_value
return total
# Example usage
roman_numeral = "MCMXCIV"
print(roman_to_int(roman_numeral)) # Output: 1994