LeetCode 12. Integer to Roman

September 01, 2022

I'm hoping we can do this in linear time, but it might end up requiring dp / backtracking.

Okay, we can do this with an ordered list of value-symbols (e.g. 1000:M, 900:CM, 500:D, ...). While our input target number is greater than 0, we append the largest possible value-symbol to our output and subtract that value from our remaining target number. e.g.

input: 2002 steps:

output: M, target: 1002
output: MM, target: 2
output: MMI, target: 1
output: MMII, target: 0

output: MMII

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_lc_examples(self):
        self.assertEqual(self.s.intToRoman(3), "III")
        self.assertEqual(self.s.intToRoman(58), "LVIII")
        self.assertEqual(self.s.intToRoman(1994), "MCMXCIV")

    def test_repeat_symbol(self):
        self.assertEqual(self.s.intToRoman(9994), "MMMMMMMMMCMXCIV")

class Solution:

    def intToRoman(self, num: int) -> str:
        res = ""
        val_to_symb = {1:"I", 4:"IV", 5:"V", 9:"IX", 10:"X", 40:"XL", 50:"L", 90:"XC", 100:"C", 400:"CD", 500:"D", 900:"CM", 1000:"M"}
        val_order = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        for v in val_order:
            count = num//v
            if not count:
                continue
            res += count*val_to_symb[v]
            num -= count*v
        return res

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