Problem
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Examples
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Solution
Method 1 - Using Hashtable Greedily
The primary challenge in counting Roman numerals arises when a numeral acts as a subtractive value rather than an additive one. For instance, in “IV”, the value of “I” (1) is subtracted from the value of “V” (5). Apart from these cases, you simply sum the values of all the numerals.
Subtractive numerals can be recognized because they appear before a larger numeral. To handle this, we track two variables: prev and curr. For IV
, prev is I
and curr is V
. When prev is less than curr, we subtract prev. After this, we continue by adding prev.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
Java
public int romanToInt(String s) {
// If the input string is null or empty, return 0
if (s == null || s.length() == 0) {
return 0;
}
// Create a map to store Roman numeral symbols and their integer values
Map<Character, Integer> map = Map.of(
'M', 1000,
'D', 500,
'C', 100,
'L', 50,
'X', 10,
'V', 5,
'I', 1
);
// Initialize sum to store the final integer value
int sum = 0;
// Initialize prev to store the value of the first Roman numeral
int prev = map.get(s.charAt(0));
// Initialize curr to store the value of the current Roman numeral
int curr = 0;
// Iterate over the string starting from the second character
for (int i = 1; i < s.length(); i++) {
// Get the value of the current Roman numeral
curr = map.get(s.charAt(i));
// If prev is less than curr, subtract prev from sum to handle the subtraction case
if (prev < curr) {
sum -= prev;
} else {
// Otherwise, add prev to sum
sum += prev;
}
// Update prev to the value of the current Roman numeral
prev = curr;
}
// Add the last processed Roman numeral value to sum
// This takes care of adding the last numeral which was not included in the loop
sum += prev;
// Return the final calculated integer value
return sum;
}
Python
def romanToInt(s: str) -> int:
# If the input string is empty, return 0
if not s:
return 0
# Create a dictionary to store Roman numeral symbols and their integer values
roman_map = {
'M': 1000,
'D': 500,
'C': 100,
'L': 50,
'X': 10,
'V': 5,
'I': 1
}
# Initialize sum to store the final integer value
sum = 0
# Initialize prev to store the value of the first Roman numeral
prev = roman_map[s[0]]
# Iterate over the string starting from the second character
for i in range(1, len(s)):
# Get the value of the current Roman numeral
curr = roman_map[s[i]]
# If prev is less than curr, subtract prev from sum to handle the subtraction case
if prev < curr:
sum -= prev
else:
# Otherwise, add prev to sum
sum += prev
# Update prev to the value of the current Roman numeral
prev = curr
# Add the last processed Roman numeral value to sum
# This takes care of adding the last numeral which was not included in the loop
sum += prev
# Return the final calculated integer value
return sum
Complexity
- ⏰ Time complexity:
O(n)
- 🧺 Space complexity:
O(1)
as we are storing 7 values in map