應用題 從羅馬數字轉成阿拉伯數字 Leetcode 13: Roman to Integer

iam_os null on Unsplash

這題的題目在這裡:

測試範例

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').
• It is guaranteed that 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