Leetcode 筆記 :(13) Roman to Integer

tags: Leetcode

題目

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, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 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.

Example 1:

Input: s = "III"
Output: 3

Example 2:

Input: s = "IV"
Output: 4

Example 3:

Input: s = "IX"
Output: 9

Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

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

思考過程

1. 一開始的想法，先創建一個字典。之後比對下一個，如果下一個比較大，那就把要減的數字記錄下來，到下一個再去減掉。但是後來發現這樣好像用太多判斷式了。

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_dict = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        
        str_len = len(s)
        result = 0 
        minus = 0
        
        for i in range(str_len):
  
            if i == str_len-1 and minus == 0:
                result += roman_dict[s[i]]
                
            elif minus !=0:
                result = result + roman_dict[s[i]] - minus
                minus = 0
            elif roman_dict[s[i]] < roman_dict[s[i+1]]:
                minus = roman_dict[s[i]]
                
            else:
                result += roman_dict[s[i]]
        return result

2. 後來想到如果我直接將字串反過來，之後直接比對他的數字如果比上一項小。那就直接減哪個數字，這樣跟上面相比就會比較精簡，時間也上升4ms。

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_dict = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        
        str_len = len(s)
        
        s = s[::-1]
        result = roman_dict[s[0]] 
        for i in range(1,str_len):

            if roman_dict[s[i]] < roman_dict[s[i-1]]:
                result -= roman_dict[s[i]]

            else:
                result += roman_dict[s[i]]
        return result