Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to make 4 and 9.Xcan be placed beforeL(50) andC(100) to make 40 and 90.Ccan be placed beforeD(500) andM(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
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.
Constraints:
1 <= s.length <= 15scontains only the characters('I', 'V', 'X', 'L', 'C', 'D', 'M').- It is guaranteed that
sis a valid roman numeral in the range[1, 3999].
Problem Description
Roman numerals are a numeral system from ancient Rome based on combinations of letters from the Latin alphabet (I, V, X, L, C, D, M) to represent numbers. Each symbol has a fixed numerical value, with I equal to 1, V equal to 5, X equal to 10, L equal to 50, C equal to 100, D equal to 500, and M equal to 1000. Numbers in Roman numerals are formed by combining these symbols and adding up their values. However, when a smaller numeral comes before a larger one, this indicates that the smaller numeral should be subtracted from the larger numeral instead of added (for example, IV means 4, not 6). This rule is used in six instances: I before V and X, X before L and C, and C before D and M. The task is to convert a string representing a Roman numeral into the integer it represents.
Intuition
To solve the problem, we should first create a mapping of Roman numeral symbols to their respective integer values. This allows for easy lookup during the conversion. To convert the Roman numeral to an integer, we can iterate over the string from left to right, checking the value of each symbol in comparison to the symbol to its right.
If a symbol is followed by one of greater value, it means we need to subtract the value of the current symbol from our result. Otherwise, we can simply add the value of the symbol. This adheres to the subtraction rule given for cases like IV or IX. To implement this in Python, we can take advantage of the pairwise utility from the itertools module, which will give us each symbol and the one following it. If the module itertools is not available or if pairwise is not a part of itertools, we can use a simple ‘zip’ technique to iterate through the symbol pairs. Then, we just need to add the value of the last symbol at the end since it’s not included in these pairwise comparisons.
The algorithm is relatively straightforward: we initialize a sum to 0 and iterate the symbols pairwise (current and next symbol). If the current is less than the next one, we subtract its value from the sum. If the current is greater than or equal to the next one, we add its value to the sum. After the loop, we catch the edge case by including the last symbol’s value, since it’s always added to the total.
Solution Approach
The solution involves a straightforward process which utilizes a hash table and a simulation algorithm based on the rules of Roman numerals.
- We define a hash table (in Python, a dictionary)
dwhich maps each Roman numeral symbol to its integer value. The key-value pairs in this dictionary are as follows:'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500, and'M': 1000. - To convert a Roman numeral string to an integer, we iterate over the string one character at a time, examining the symbol and the one that follows it (this is the pairwise comparison). For this task, we use a for loop in conjunction with the Python generator expression format. To demonstrate, we generate tuples of (current character
a, next characterb) using the pairwise utility or a manual method by zipping the string with itself offset by one character. - In this iteration, we compare the integer value of the current symbol with the value of the symbol following it. If the current value is less than the next, we should deduct its value from the total sum since it indicates subtraction as per Roman numerals (e.g.,
IVfor 4). If the current value is equal to or greater than the following symbol’s value, we add it to the total sum. - The comparison
(d[a] < d[b])returns a boolean, and in the solution, it is used to determine whether the value will be subtracted-1 * d[a]or added1 * d[a]. We use a sum function to add all these values together. - As the pairwise comparison does not include the very last symbol in the computation, we correct for this by adding
d[s[-1]]to the total sum to include the value of the last symbol. - The final sum that results from this process is the integer value of the provided Roman numeral string.
To demonstrate the implementation of our approach with the code:
class Solution:
def romanToInt(self, s: str) -> int:
d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
total = sum((-1 if d[a] < d[b] else 1) * d[a] for a, b in pairwise(s)) + d[s[-1]]
return totalIn the above code, pairwise(s) would need to be replaced by an equivalent if it’s not available in the standard Python library: zip(s, s[1:]). Here, zip pairs each character with the next, effectively creating the needed pairwise functionality.
# If pairwise is not inbuilt, we can define our own pairwise function like this:
from itertools import tee
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
# Alternatively, we can modify the loop in the main function to not need pairwise:
class Solution:
def romanToInt(self, s: str) -> int:
d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
total, prev_value = 0, 0
for char in reversed(s):
if d[char] < prev_value:
total -= d[char]
else:
total += d[char]
prev_value = d[char]
return totalBy adapting the algorithm to avoid using the pairwise utility, we ensure compatibility with the Python standard library without relying on any external or updated modules.
Example Walkthrough
Let’s use the Roman numeral MCMIV as an example to illustrate the solution approach, which translates to 1904 in integer form. This number is chosen because it includes subtraction instances (CM and IV).
Following the solution approach steps:
- We create a dictionary called
dthat maps each Roman numeral to its integer value:d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} - We start iterating over the Roman numeral string “MCMIV” using pairs:
- Pair MC (M=1000, C=100)
- Pair CM (C=100, M=1000)
- Pair MI (M=1000, I=1)
- Pair IV (I=1, V=5)
- We compare the values of each pair:
- For MC, 1000 is greater than 100, so we add 1000.
- For CM, 100 is less than 1000, so we subtract 100.
- For MI, 1000 is greater than 1, so we add 1000.
- For IV, 1 is less than 5, so we subtract 1.
- We perform the addition and subtraction as directed:
- Starting sum is 0.
- Add M (1000) = 1000.
- Subtract C (100) from sum (900).
- Add M (1000) to sum (1900).
- Subtract I (1) from sum (1899).
- We add the last character value (V=5) to the sum since the pairwise comparison above doesn’t account for it:
- The final sum is 1899 + 5 = 1904, which is the integer equivalent of “MCMIV”.
This methodically breaks down the input string, using the subtraction rule as needed, and continues to accumulate the total to reach the correct conversion from Roman numeral to integer.
Solution Implementation
class Solution {
public:
int romanToInt(string s) {
int res = 0; // Initialize result to 0
// Map each Roman numeral to its integer value
unordered_map <char, int> roman = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
// Iterate through the string except for the last character
for (int i = 0; i < s.size() - 1; i++) {
// If the current numeral is less than the next numeral, subtract it from result
if (roman[s[i]] < roman[s[i + 1]]) {
res -= roman[s[i]];
} else {
// Otherwise, add the value of the current numeral to result
res += roman[s[i]];
}
}
// Add the value of the last numeral to the result
return res + roman[s[s.size() - 1]];
}
};class Solution {
public int romanToInt(String s) {
int res = 0; // Initialize the result to 0
Map<Character, Integer> roman = new HashMap<>(); // Create a map to store Roman numeral values
roman.put('I', 1);
roman.put('V', 5);
roman.put('X', 10);
roman.put('L', 50);
roman.put('C', 100);
roman.put('D', 500);
roman.put('M', 1000);
// Loop through the string, except the last character
for (int i = 0; i < s.length() - 1; i++) {
// If the current numeral is less than the next numeral, subtract it from result
if (roman.get(s.charAt(i)) < roman.get(s.charAt(i + 1))) {
res -= roman.get(s.charAt(i));
} else {
// Otherwise, add the value of the current numeral to result
res += roman.get(s.charAt(i));
}
}
// Add the value of the last numeral to the result
return res + roman.get(s.charAt(s.length() - 1));
}
}class Solution:
def romanToInt(self, s: str) -> int:
res = 0 # Initialize result to 0
roman = { # Mapping of Roman numeral characters to their integer values
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
# Iterate through the string in pairs of consecutive characters
for a, b in zip(s, s[1:]):
# If the current numeral is less than the next, subtract it from the result
if roman[a] < roman[b]:
res -= roman[a]
else:
# Otherwise, add the value of the current numeral to the result
res += roman[a]
# Add the value of the last numeral to the result
return res + roman[s[-1]]int val(char c) {
switch(c) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
int romanToInt(char* s) {
int res = 0; // Initialize the result
int i;
for (i = 0; s[i] != '\0'; i++) {
// If the current value is less than the next value, subtract it
if (val(s[i]) < val(s[i + 1])) {
res -= val(s[i]);
} else {
// Otherwise, add it
res += val(s[i]);
}
}
return res;
}public class Solution {
// Method to convert Roman numeral string to integer
public int RomanToInt(string s) {
int ans = 0; // Initialize result to 0
// Loop through each character in the string
for (int i = 0; i < s.Length; i++) {
int currentVal = value(s[i]); // Get the integer value of the current Roman numeral
int nextVal = i < s.Length - 1 ? value(s[i + 1]) : 0; // Get the integer value of the next Roman numeral (or 0 if at the end)
// If the current numeral is less than the next, subtract its value from result
if (currentVal < nextVal) ans -= currentVal;
else ans += currentVal; // Otherwise, add its value to result
}
return ans; // Return the final result
}
// Helper method to return the integer value of a Roman numeral character
public int value(char c) => c switch
{
'I' => 1,
'V' => 5,
'X' => 10,
'L' => 50,
'C' => 100,
'D' => 500,
'M' => 1000,
_ => 0 // Return 0 for any non-Roman characters (default case)
};
}var romanToInt = function(s) {
let res = 0; // Initialize result to 0
const roman = { // Mapping of Roman numeral characters to their integer values
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
// Loop through the string except for the last character
for (let i = 0; i < s.length - 1; i++) {
// If the current numeral is less than the next, subtract its value from result
if (roman[s[i]] < roman[s[i + 1]]) {
res -= roman[s[i]];
} else {
// Otherwise, add the value of the current numeral to result
res += roman[s[i]];
}
}
// Add the value of the last numeral to the result
return res + roman[s[s.length - 1]];
};function romanToInt(s: string): number {
let result = 0; // Initialize the result to 0
let prevValue = 0; // Initialize the previous numeral value to 0
const romanValues: { [key: string]: number } = { // Mapping of Roman numeral characters to their integer values
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
// Iterate through the string from right to left (starting from the last character)
for (let i = s.length - 1; i >= 0; i--) {
const currValue = romanValues[s[i]]; // Get the integer value of the current numeral
// If the current numeral value is less than the previous one, subtract it from result
if (currValue < prevValue) {
result -= currValue;
} else {
// Otherwise, add the value of the current numeral to the result
result += currValue;
}
prevValue = currValue; // Update the previous numeral value to the current one
}
// Return the final result
return result;
};class Solution {
/**
* @param String $s
* @return Integer
*/
function romanToInt($s) {
$romanKeys = array('I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100, 'D' => 500, 'M' => 1000);
$letters = str_split($s);
$kount = count($letters);
$out = 0;
// Start at the end and go forward.
for ($i = $kount - 1; $i >= 0; $i--) {
$letter = $letters[$i];
// Add the matching amount.
$out += $romanKeys[$letter];
// If there is a previous letter, check for subtraction.
if ($i > 0) {
$prevLetter = $letters[$i-1];
// Subtract values of there related prefix letters.
if ($prevLetter === 'I' && in_array($letter, ['V','X'])) {
$out -= 1;
$i--;
}
if ($prevLetter === 'X' && in_array($letter, ['L','C'])) {
$out -= 10;
$i--;
}
if ($prevLetter === 'C' && in_array($letter, ['D','M'])) {
$out -= 100;
$i--;
}
}
}
return $out;
}
}class Solution {
func romanToInt(_ s: String) -> Int {
// Dictionary to map Roman numeral characters to their integer values
let dict: [Character:Int] = ["I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000]
var out = 0, prev = 0 // Initialize output and previous numeral values
// Loop through each character in the string
for i in s {
let val = dict[i] ?? 0 // Get the integer value for the current numeral (default to 0 if not found)
// If the current value is less than or equal to the previous one, add it to the result
// Otherwise, subtract the previous value (indicating the subtractive notation)
out += (val <= prev) ? prev : -prev
prev = val // Update previous numeral value to the current one
}
out += prev // Add the value of the last numeral to the result
return out // Return the final result
}
}class Solution {
// Function to convert Roman numeral string to integer
fun romanToInt(s: String) = s.mapIndexed { i, c ->
// Multiply the Roman value of the current character by either 1 or -1
// If the next character's value is less than or equal to the current, add the value; otherwise, subtract it
c.roman * if ((s.getOrNull(i + 1)?.roman ?: 0) <= c.roman) 1 else -1
}.sum() // Sum up all the values calculated
// Extension property to get the integer value of a Roman numeral character
private val Char.roman
get() = when (this) {
'I' -> 1
'V' -> 5
'X' -> 10
'L' -> 50
'C' -> 100
'D' -> 500
'M' -> 1000
else -> 0 // Return 0 for any non-Roman characters (default case)
}
}class Solution {
int romanToInt(String s) {
int ans = 0, num = 0;
for (int i = s.length-1; i >= 0; i--) {
switch(s[i]) {
case 'I': num = 1; break;
case 'V': num = 5; break;
case 'X': num = 10; break;
case 'L': num = 50; break;
case 'C': num = 100; break;
case 'D': num = 500; break;
case 'M': num = 1000; break;
}
if (4 * num < ans) ans -= num;
else ans += num;
}
return ans;
}
}func romanToInt(s string) int {
// Maping single roman numeral to decimal values
romanVals := map[rune]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
// Decimal value to be returned
calcVal := 0
// Looping over roman numeral string
for i := 0; i < len(s); i++ {
// First roman numeral just add to total
if i == 0 {
calcVal += romanVals[rune(s[i])]
// If previous roman numeral value is less than current one
// then substract the previous roman numeral value from calcVal
// then add the current roman value substracted by the previous
// roman numeral to calcVal
} else if romanVals[rune(s[i])] > romanVals[rune(s[i-1])] {
calcVal -= romanVals[rune(s[i-1])]
calcVal += romanVals[rune(s[i])] - romanVals[rune(s[i-1])]
// If previous value is greater than just add the current roman
// value to calcVal
} else {
calcVal += romanVals[rune(s[i])]
}
}
return calcVal
}Time and Space Complexity
The time complexity of the given code can be analyzed based on the operations performed on the input string s. The function iterates over pairs of adjacent characters in the string, which is done by pairwise(s). Since pairwise essentially goes through the entire string once to create these pairs, the number of operations will be proportional to the length of the string n. Therefore, the time complexity is O(n).
In terms of space complexity, the auxiliary space used by the algorithm is for the dictionary d that stores the Roman numerals and their corresponding integer values. The size of d is constant, as there are a fixed number of Roman numerals. However, pairwise(s) generates an iterator which does not store all pairs in memory at once, hence it does not add to the space complexity. Therefore, the space complexity remains constant, not dependent on the length of the input string, and can be denoted as O(1), rather than O(m), since m would imply a dependency on the size of the character set that isn’t present here.