A Space Efficient Solution


  • 0
    R

    This solution reflects the rules of roman numbers and uses it to construct a roman number. You don't need a very large dictionary or hash map. All you have to store is 1, 5 for every digit. And it uses a loop to decide which digit it is at, instead of hard coding. Again, this solution might be time consuming(128ms) but space efficient.

    class Solution(object):
        def intToRoman(self, num):
            d = {1: {1:'I', 5:'V'}, 
                 10: {1:'X', 5:'L'}, 
                 100: {1:'C', 5:'D'},
                 1000: {1:'M',},}
            roman = ""
            length = len(str(num))
            for i in range(length, -1, -1):
                digit = 10**i
                value = num/digit
                if value == 0:
                    continue
                elif value == 4:
                    roman += d[digit][1] + d[digit][5]
                elif value == 9:
                    roman += d[digit][1] + d[digit*10][1]
                elif value >0 and value < 4:
                    roman += value*d[digit][1]
                elif value >= 5 and value<9:
                    roman += d[digit][5] + (value-5)*d[digit][1]
                else:
                    print 'wrong input'
                    return
                num %= digit
            return roman
    

Log in to reply
 

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