13.Roman to Integer

Tags: [roman], [int], [trick], [map], [knowledge]

Com: {fb}

Link: https://leetcode.com/problems/roman-to-integer/\#/description

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Solution: Trick

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            raise ValueError('the input is invald')

        romans = {
            'M': 1000,
            'D': 500,
            'C': 100,
            'L': 50,
            'X': 10,
            'V': 5,
            'I': 1
        }

        result = 0
        for i in xrange(len(s) - 1):
            curr = s[i]
            next = s[i + 1]

            if romans[curr] < romans[next]:
                result -= romans[curr]
            else:
                result += romans[curr]

        return result + romans[s[-1]]

Revelation:

• Think about the case 'IV', the curr = 'I' and next = 'V', romans[curr] < romans[next], so here we should do result -= 1, because next round the result will be result += 5.
• Think about the case 'VI', the curr = 'V' and next = 'I', romans[curr] > romans[next], so here we should do result += 5, because next round number will not 'include' this round number.
• We will always add the last number to result.

Note:

• Time complexity = O(n), n is the length of the given string.
• Space complexity = O(1).