Model answer
The task
Convert a string of Roman numeral symbols into its integer value. Roman numerals use a small set of symbols, with some smaller values placed before larger ones to indicate subtraction.
Key idea
Scan the string from left to right, comparing each symbol’s value with the next one. If the current value is smaller, subtract it; otherwise, add it. This handles subtractive pairs without needing to process them separately.
Approach
- Store the integer value for each Roman numeral symbol in a lookup table.
- Initialize a running total to zero.
- For each symbol, compare its value with the following symbol’s value, if one exists.
- Subtract the current value when it is smaller than the next value; otherwise, add it.
- Return the total. This assumes the input is a valid Roman numeral.
class Solution:
def romanToInt(self, s: str) -> int:
values = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
total = 0
for i, symbol in enumerate(s):
current = values[symbol]
# A smaller value before a larger value is subtracted.
if i + 1 < len(s) and current < values[s[i + 1]]:
total -= current
else:
total += current
return total
Complexity: Time: O(n), where n is the string length, since each symbol is visited once.
Complexity: Space: O(1), because the lookup table has a fixed number of entries.
Common follow-ups
- How would you handle invalid Roman numeral strings? Validate symbol order and repetition rules before or during conversion.
- How would you convert an integer to a Roman numeral? Greedily subtract from a descending list of allowed values, including subtractive pairs.
- Can the conversion be done scanning right to left? Yes; subtract a value if it is smaller than the largest value already seen to its right, otherwise add it.