# LeetCode 13: Roman to Integer ## Problem Restatement We are given a Roman numeral string `s`. We need to convert it into an integer. Roman numerals use seven symbols: | Symbol | Value | |---|---:| | `I` | 1 | | `V` | 5 | | `X` | 10 | | `L` | 50 | | `C` | 100 | | `D` | 500 | | `M` | 1000 | Usually, Roman numerals are written from largest to smallest. For example: ```text VIII = 5 + 1 + 1 + 1 = 8 ``` But there are six subtractive cases: | Roman | Value | |---|---:| | `IV` | 4 | | `IX` | 9 | | `XL` | 40 | | `XC` | 90 | | `CD` | 400 | | `CM` | 900 | The input is guaranteed to be a valid Roman numeral in the range `[1, 3999]`. The string length is between `1` and `15`, and it contains only `I`, `V`, `X`, `L`, `C`, `D`, and `M`. ## Input and Output | Item | Meaning | |---|---| | Input | A valid Roman numeral string `s` | | Output | The integer value of `s` | | Constraint | `1 <= s.length <= 15` | | Range | Roman numeral represents a value in `[1, 3999]` | Example function shape: ```python def romanToInt(s: str) -> int: ... ``` ## Examples Example 1: ```text s = "III" ``` Value: ```text 1 + 1 + 1 = 3 ``` Output: ```text 3 ``` Example 2: ```text s = "LVIII" ``` Break it down: ```text L = 50 V = 5 III = 3 ``` Total: ```text 50 + 5 + 3 = 58 ``` Output: ```text 58 ``` Example 3: ```text s = "MCMXCIV" ``` Break it down: ```text M = 1000 CM = 900 XC = 90 IV = 4 ``` Total: ```text 1000 + 900 + 90 + 4 = 1994 ``` Output: ```text 1994 ``` ## First Thought: Check Special Pairs Manually One direct approach is to scan the string and check whether the current character and the next character form one of the six subtractive pairs: ```text IV, IX, XL, XC, CD, CM ``` If we see one of these pairs, add its special value and skip two characters. Otherwise, add the value of the current symbol and move one character. This works. But there is an even simpler rule. ## Key Insight When a smaller Roman value appears before a larger Roman value, we subtract it. Otherwise, we add it. For example: ```text IV ``` `I` is smaller than `V`, so: ```text -1 + 5 = 4 ``` For: ```text VI ``` `V` is larger than `I`, so: ```text 5 + 1 = 6 ``` So for each symbol: - if its value is less than the next symbol's value, subtract it - otherwise, add it This rule correctly handles all six subtractive cases. ## Visual Walkthrough Use: ```text s = "MCMXCIV" ``` Map each symbol: ```text M = 1000 C = 100 M = 1000 X = 10 C = 100 I = 1 V = 5 ``` Now scan left to right. `M` is followed by `C`. ```text 1000 >= 100 add 1000 ``` `C` is followed by `M`. ```text 100 < 1000 subtract 100 ``` `M` is followed by `X`. ```text 1000 >= 10 add 1000 ``` `X` is followed by `C`. ```text 10 < 100 subtract 10 ``` `C` is followed by `I`. ```text 100 >= 1 add 100 ``` `I` is followed by `V`. ```text 1 < 5 subtract 1 ``` `V` is the last symbol, so add it. Total: ```text 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994 ``` ## Algorithm 1. Store Roman symbol values in a dictionary. 2. Initialize `total = 0`. 3. Scan every character by index. 4. For each character: - get its value - if the next character exists and has a larger value, subtract current value - otherwise, add current value 5. Return `total`. ## Correctness The Roman numeral is valid, so every subtractive case appears as a smaller symbol before a larger symbol. The algorithm detects exactly that situation by comparing the current value with the next value. If the current value is smaller than the next value, the current symbol contributes negatively as part of a subtractive pair. Otherwise, the current symbol contributes normally and is added. Every symbol is processed once. For additive groups such as `VIII`, all symbols are added. For subtractive groups such as `IV`, the first symbol is subtracted and the second symbol is added, producing the correct value. Therefore the final total equals the integer represented by the Roman numeral. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n)` | We scan the string once | | Space | `O(1)` | The value map has fixed size | Since `s.length <= 15`, this is constant-bounded for the original constraints. ## Implementation ```python 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 in range(len(s)): current = value[s[i]] if i + 1 < len(s) and current < value[s[i + 1]]: total -= current else: total += current return total ``` ## Code Explanation The dictionary stores the value of each Roman symbol: ```python value = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000, } ``` We scan the string by index: ```python for i in range(len(s)): ``` For each symbol, read its value: ```python current = value[s[i]] ``` If the next symbol exists and is larger: ```python if i + 1 < len(s) and current < value[s[i + 1]]: ``` then this symbol is part of a subtractive pair, so subtract it: ```python total -= current ``` Otherwise, add it: ```python total += current ``` Finally: ```python return total ``` ## Testing ```python def run_tests(): s = Solution() assert s.romanToInt("III") == 3 assert s.romanToInt("LVIII") == 58 assert s.romanToInt("MCMXCIV") == 1994 assert s.romanToInt("IV") == 4 assert s.romanToInt("IX") == 9 assert s.romanToInt("XL") == 40 assert s.romanToInt("XC") == 90 assert s.romanToInt("CD") == 400 assert s.romanToInt("CM") == 900 assert s.romanToInt("MMMCMXCIX") == 3999 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `"III"` | Repeated additive symbols | | `"LVIII"` | Mixed additive symbols | | `"MCMXCIV"` | Multiple subtractive cases | | `"IV"` | Ones-place subtractive case | | `"IX"` | Ones-place subtractive case | | `"XL"` | Tens-place subtractive case | | `"XC"` | Tens-place subtractive case | | `"CD"` | Hundreds-place subtractive case | | `"CM"` | Hundreds-place subtractive case | | `"MMMCMXCIX"` | Maximum value, 3999 |