Roman numerals use the symbols I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Values are usually written from largest to smallest and added, but a smaller symbol placed before a larger one is subtracted (IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900). Given a valid Roman numeral s, return its integer value.
- 1 <= s.length <= 15
- `s` is a valid Roman numeral in the range 1 to 3999
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
One approach lists all 13 symbol pairs and singles and matches greedily, but there is a simpler rule. Normally values decrease from left to right and we just add them. The only exception is a smaller value placed directly before a larger one, and in that case the smaller value counts as negative. So scan once, and for each symbol add its value, or subtract it if the next symbol is bigger.
Algorithm
- Map each symbol to its value.
- For each index
i, letv = value[s[i]]. - If
i + 1 < nandvalue[s[i+1]] > v, subtractv; otherwise add it. - Return the total.
O(n)Space: O(1)class Solution: def romanToInt(self, s: str) -> int: value = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} total = 0 for i, c in enumerate(s): v = value[c] # A smaller symbol before a larger one is subtracted. if i + 1 < len(s) and value[s[i + 1]] > v: total -= v else: total += v return total