0013 - Roman to Integer

Difficulty

Easy

Language

Python

URL

https://leetcode.com/problems/roman-to-integer/

Solution 1 - Hash Map with Subtraction Rule

Iterate through the string character by character. For each pair of adjacent characters, if the current value is less than the next value, subtract it (handles cases like IV = 4, IX = 9). Otherwise, add it. Finally, add the last character's value.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0013.1 - Roman to Integer - Solution 1 - Hash Map with Subtraction Rule """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def romanToInt(self, s: str) -> int:
        """Roman to Integer Function"""
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        ans = 0

        for a, b in zip(s, s[1:]):
            if roman[a] < roman[b]:
                ans -= roman[a]
            else:
                ans += roman[a]

        return ans + roman[s[-1]]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().romanToInt("III"))       # 3
    print(Solution().romanToInt("LVIII"))     # 58
    print(Solution().romanToInt("MCMXCIV"))   # 1994


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Right-to-Left Traversal

Traverse the string from right to left. If the current character's value is less than the previous character's value (the one to its right), subtract it. Otherwise, add it. This naturally handles the subtraction rule without needing to look ahead.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0013.2 - Roman to Integer - Solution 2 - Right-to-Left Traversal """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def romanToInt(self, s: str) -> int:
        """Roman to Integer Function"""
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        ans = 0
        prev = 0

        for ch in reversed(s):
            curr = roman[ch]
            if curr < prev:
                ans -= curr
            else:
                ans += curr
            prev = curr

        return ans


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().romanToInt("III"))       # 3
    print(Solution().romanToInt("LVIII"))     # 58
    print(Solution().romanToInt("MCMXCIV"))   # 1994


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()