[LeetCode with Python] 13. Roman to Integer

Difficulty: Easy

 

First Approach: to deal with exception cases(e.g. "IV"), use before_map to know there is next letter to check. -> inefficent in memory usage.

 

Second Approach(reference from https://medium.com/@angelahiking/13-roman-to-integer-python-easy-cabcb1d6b8a3):

The idea is, in exception cases there always comes "smaller" number before "larger" number. So we don't need before_map, and just judge whether "smaller" number comes before "larger" number.

 

num_map = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}
before_map = {
    "C": ["D", "M"],
    "X": ["L", "C"],
    "I": ["V", "X"],
    "M": [],
    "D": [],
    "L": [],
    "V": [],
}


class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        for i in range(len(s)):
            letter = s[i]
            if i + 1 < len(s) and num_map[letter] < num_map[s[i + 1]]:
                sum -= num_map[letter]
            else:
                sum += num_map[letter]
        return sum


if __name__ == "__main__":
    solution = Solution()
    print(solution.romanToInt("LVIII"))

 

Test code:

import unittest
import solution


class Test(unittest.TestCase):
    def setUp(self):
        self.instance = solution.Solution()

    def test(self):
        result = self.instance.romanToInt("LVIII")
        self.assertEqual(result, 58)

    def test2(self):
        result = self.instance.romanToInt("III")
        self.assertEqual(result, 3)

    def test3(self):
        result = self.instance.romanToInt("IV")
        self.assertEqual(result, 4)

    def test4(self):
        result = self.instance.romanToInt("MCMXCIV")
        self.assertEqual(result, 1994)


testSuite = unittest.TestSuite()
for testmethod in ("test", "test2", "test3", "test4"):
    testSuite.addTest(Test(testmethod))
runner = unittest.TextTestRunner()
runner.run(testSuite)