Easy to read recursive Python (17 lines)


  • 0
    A
    class Solution(object):
        dict = { 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'}
        def intToRoman(self, num):
            str = ''
            list = [10, 100, 1000, 10000]   #get the tens/hundreds/thousands place
            for i in list:
                if num % i != 0:
                    str = self.compute(num % i, i/10) + str
                    num = num - (num % i)
            return str
            
        def compute(self, num, lsb):
            if num in self.dict:
                return self.dict[num]
            else:
                return self.compute(num-lsb, lsb) + self.dict[lsb]
    

    takes 112 ms, but is way more readable than most solutions on here.
    look at the LSB, and then recursively determine which numeral to concat onto the main string, before looking at the next LSB.
    for a number like 8, it will decrement by some number (1, 10, etc) depending on which place (tens, hundreds) it is looking at until it gets to a number in the dict, meaning whole numbers or numbers like 4, 9, etc


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.