Double subtraction?


  • 0
    B
    def romanToInt(self,s):
        if not s:
            return 0
    
        result=0
    
        map={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
    
        length=len(s)
        old=map[s[length-1]]
    
        for i in range(1,length):
            current=map[s[length-1-i]]
            if current>=old:
                result+=old
                old=current
            else:
                old-=current
    
        print(result+old)
    

    I was doing addition from right to left. while i found any numeral smaller than the previous one (that has not been processed), it means a subtraction.
    i.e.:
    IIV means 3, VIIIV means V(IIIV) not (VIII)V.

    But i am not sure if this is indeed the rule for roman numerals? Always perform from right to left and do subtraction before addition?


  • 0
    C

    Assuming that the given roman numerals are correct (and it is in fact the case in all the test-cases), you are guaranteed your algorithm works. ie. subtract if current < old.

    The reason is numerals like : VMMXV are invalid. The subtraction forms IV, IX, XL, XC, CD and CM always follows the next largest number. Wiki

    However, if your are to validate while converting Roman to integer. You need additional checks like keeping track of repeating literals. For example, the above algorithm gives "VVVVV" => 25 which is invalid.


Log in to reply
 

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