題目會給定我們一組羅馬數字,要求我們把它轉換為對應十進位表示法的阿拉伯數字。
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15
s
contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M')
.s
is a valid roman numeral in the range [1, 3999]
.把原本題目給的羅馬數字和十進位數字的關係建立成一張映射表(字典)。
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
遇到對應的符號,就把對應的十進位數字做相加。
唯一一個實作的細節是,遇到逆序排列(小的羅馬數字在前,大的羅馬數字在後)的情況時,要記得把小的那項*2補扣掉。
例如,遇到IV時,IV是逆續,所以要把比較小的那項I*2補扣掉。
IV = 10 + 50 - 2*10 = 60 - 20 = 40
class Solution:
def romanToInt(self, s: str) -> int:
# key: roman symbol
# value: decimal value
mapping_table = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
# integer value
number = 0
# scan each roman symbol
for idx, char in enumerate(s):
# add corresponding value
number += mapping_table[char]
if idx and ( mapping_table[char] > mapping_table[ s[idx-1] ] ):
# adjustment for IV, IX, XL, XC, CD, CM
number -= 2 * mapping_table[ s[idx-1] ]
return number
時間複雜度: O( n)
從左到右,每個羅馬數字掃描過一遍。
空間複雜度: O(1)
都是臨時變數,所占用的記憶體空間為常數級別O(1)
想到用字典(雜湊映射表),去儲存每個羅馬數字和十進位表示裡面對應到的阿拉伯數字的映射關係。
另外,還有一個實作的細節是,遇到逆序排列(小羅馬數字的在前,大的羅馬數字在後)的情況時,要記得把小的那項*2補扣掉。
Reference:
[1] Python O(n) by dictionary and math [w/ Hint] - Roman to Integer - LeetCode