Roman numerals are a numeral system that originated in ancient Rome and are still used today in various contexts, such as clock faces, book chapters, and movie sequels. The Roman numeral system consists of seven basic symbols, each with a corresponding numerical value: I, V, X, L, C, D, and M.
In this article, we will explore the problem of converting a given Roman numeral to an integer, as presented on LeetCode. We will provide solutions in both C++ and Python and analyze their time and space complexities.
Problem Statement
Given a string s representing a Roman numeral, convert it to an integer.
Examples
Input: s = "III" Output: 3
Input: s = "IX" Output: 9
Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
C++ Solution
The following C++ code uses an unordered map to store the numerical values of each Roman numeral. It then iterates through the input string and adds or subtracts the corresponding values to obtain the final integer value.
class Solution {
public:
int romanToInt(string s) {
int sum = 0;
unordered_map<char,int> conv = {
{'I',1},
{'V',5},
{'X',10},
{'L',50},
{'C',100},
{'D',500},
{'M',1000}
};
for(int i=0; i<s.size(); i++){
if( conv[s[i]] < conv[s[i+1]] ){
sum += conv[s[i+1]] - conv[s[i]];
i++;
}
else
sum += conv[s[i]];
}
return sum;
}
};
The time complexity of this solution is O(n), where n is the length of the input string, since we iterate through the string once. The space complexity is O(1), since we use a fixed-size unordered map.
Python Solution
The following Python code uses functools.reduce to iterate through the input string in reverse order and accumulate the integer value. We use a lookup table to store the numerical values of each Roman numeral and an operator dictionary to perform addition or subtraction based on the current and previous values.
import functools as fn
import operator as op
class Solution:
lookup_table = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
ops = {
False: op.add,
True: op.sub
}
def romanToInt(self, s: str) -> int:
_, result = fn.reduce(
lambda state, c:
(lambda num, prev_num, result:
(num, self.ops[prev_num > num](result, num))
)(self.lookup_table[c], *state),
s[::-1],
(0, 0) # prev_num, result
)
return result
The above Python code defines a Solution class with a romanToInt method that takes in a string s representing a Roman numeral and returns an integer.
The solution uses a lookup table that maps each Roman numeral to its corresponding integer value. It then iterates through the string s, keeping track of the current and previous integer values. If the current integer value is greater than the previous integer value, it subtracts the previous integer value from the result. Otherwise, it adds the current integer value to the result.
Overall, the time complexity of this solution is O(n), where n is the length of the input string s. The space complexity is also O(1), since we only use a constant amount of extra space to store the lookup table and some variables.
In contrast to the previous solution, this one avoids the use of explicit looping constructs and instead leverages Python's reduce function for a more functional approach.
In conclusion, this problem shows the importance of being able to effectively map between different representations of numbers. By using a lookup table and some basic math operations, we can efficiently convert Roman numerals to integers.