a look-up table solution with python


  • 0
    M

    I figure out a straight look-up table solution... No more thinking on meaningless "effecient decoding" of roman numbers... Since lookup table is generate beforehand the actual running time is O(1).

    def gen(a,b,c):
        return ["", a, a+a, a+a+a, a+b, b, b+a, b+a+a, b+a+a+a, a+c]
    m = [gen("I","V","X"),gen("X","L","C"), gen("C","D","M"), gen("M","","")]
    r_total_m = dict()
    for i in range(4):
        for j in range(10):
            for k in range(10):
                for l in range(10):
                    r_total_m[m[3][i]+m[2][j]+m[1][k]+m[0][l]]=i*1000+j*100+k*10+l
                    
    
    class Solution(object):
        def romanToInt(self, s):
            """
            :type s: str
            :rtype: int
            """
            return r_total_m[s]
    

Log in to reply
 

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