Leetcode 13 - Roman to Integer

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Explanation
  3. 3. Code

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.
  • Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: “III”
Output: 3
Example 2:

Input: “IV”
Output: 4
Example 3:

Input: “IX”
Output: 9
Example 4:

Input: “LVIII”
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.
Example 5:

Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Explanation

因为包含特殊组合的罗马数字表示不同的含义，因此需要对 IXC 单独进行判断，但是常规方式的判断语句太多，不太简洁。简单的方式是将罗马数字逆序来看，如果是正常情况，则每一位罗马数字都应该不小于前一位，即 nums[i] >= nums[i-1]。但如果需要通过组合表示 -1,-10,-100 的操作，则会出现当前一位罗马数字比前一位小的情况，例如 IV 的逆序 VI。nums[1] 小于 nums[0]，说明这里需要减去 nums[1] 即 1。重复以上的操作，当前位置数字大于等于前一位时，正常叠加，否则减去当前数字。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        dic = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        pre = 0
        res = 0
        for x in s[::-1]:
            if dic[x] < pre:
                res -= dic[x]
            else:
                res += dic[x]
                pre = dic[x]
        return res
Comments