LeetCode 13. Roman to Integer

August 31, 2022

We can do this in a single greedy pass. We can handle the two-character values by peeking ahead one character.

A way to think about this is: A symbol should be treated as negative if it is followed by a larger symbol.

The last symbol will never be negative, so our result can always have that added. Then we can just iterate over $i \epsilon [0, n-2]$ and peek ahead one index to decide whether to negate the value at $i$ .

The runtime of this algorithm is $O(n)$ and the space complexity is $O(1)$ .

import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_single(self):
        self.assertEqual(self.s.romanToInt("I"), 1)
        self.assertEqual(self.s.romanToInt("V"), 5)
        self.assertEqual(self.s.romanToInt("X"), 10)
        self.assertEqual(self.s.romanToInt("L"), 50)
        self.assertEqual(self.s.romanToInt("C"), 100)
        self.assertEqual(self.s.romanToInt("D"), 500)
        self.assertEqual(self.s.romanToInt("M"), 1000)

    def test_longer(self):
        self.assertEqual(self.s.romanToInt("MCMXCIV"), 1994)

class Solution:

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

if __name__=="__main__":
    unittest.main()