13. Roman to Integer

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Example 2

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Solution 1: Brute-Force + Hash

class Solution:
    def romanToInt(self, s: str) -> int:
        symbolToValue = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        
        sumVal = 0
        for i in range(len(s) - 1):
            if symbolToValue[s[i]] >= symbolToValue[s[i + 1]]:
                sumVal += symbolToValue[s[i]]
            else:
                sumVal -= symbolToValue[s[i]]
        sumVal += symbolToValue[s[-1]]
        return sumVal

Time Complexity: O(N)
Space Complexity: O(1) // The size of symbol table is constant

Solution 2: String Replace

class Solution:
    def romanToInt(self, s: str) -> int:
        s = s.replace('IV', 'I' * 4).replace('IX', 'I' * 9)
        s = s.replace('XL', 'I' * 40).replace('XC', 'I' * 90)
        s = s.replace('CD', 'I' * 400).replace('CM', 'I' * 900)
        s = s.replace('V', 'I' * 5)
        s = s.replace('X', 'I' * 10)
        s = s.replace('L', 'I' * 50)
        s = s.replace('C', 'I' * 100)
        s = s.replace('D', 'I' * 500)
        s = s.replace('M', 'I' * 1000)
        return len(s)

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: String Replace + Hash

class Solution:
    def romanToInt(self, s: str) -> int:
        symbolToVal = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        s = s.replace('IV', 'IIII').replace('IX', 'VIIII')
        s = s.replace('XL', 'XXXX').replace('XC', 'LXXXX')
        s = s.replace('CD', 'CCCC').replace('CM', 'DCCCC')
        sum = 0
        for sym in s:
            sum += symbolToVal[sym]
        return sum

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/roman-to-integer/discuss/264743/Clean-Python-beats-99.78.

Follow-up: 12. Integer to Roman