Leetcode 13. Roman to Integer

###### tags: `Math` <h1> Leetcode 13. Roman to Integer </h1> <ol> <li>問題描述</li> 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 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: <ul> <li>I can be placed before V (5) and X (10) to make 4 and 9.</li> <li>X can be placed before L (50) and C (100) to make 40 and 90.</li> <li>C can be placed before D (500) and M (1000) to make 400 and 900.</li> </ul> Given a roman numeral, convert it to an integer. Example: Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. <li>Input的限制</li> <ul> <li>1 <= s.length <= 15</li> <li>s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').</li> <li>It is guaranteed that s is a valid roman numeral in the range [1, 3999].</li> </ul> 在 leetcode 的此題中，所有的 input 都是 valid 的。在實際上的情況中，可能要考慮使用者輸入錯誤的狀況。 <li>思考流程</li> <ul> <li>由左到右遍歷 + if-else 考慮所有的情況</li> 從左到右遍歷整個字串，先辨認 s[i] 代表什麼整數，然後直接累積加到要 return 的變數裡，並同時檢查 s[i] 是否大於 s[i-1]，若 s[i] > s[i-1]，則要扣除兩倍的 s[i-1] (因為前面有把s[i-1]累加起來，所以除了依照原本羅馬數字的規則要減去 s[i-1] 外，還要把多加的扣掉)。 Big-Oh ： Let f (n) and g(n) be functions mapping nonnegative integers to real numbers. We say that f (n) is O(g(n)) if there is a real constant c > 0 and an integer constant n0 ≥ 1 such that f (n) ≤ cg(n), for n ≥ n0. 根據上述的定義，n 的定義域是正整數的範圍。但如果我們的 input 是有限域，則我們總是能找到一個常數 c 大於所有從有限域映射出來的 f(n)，故在這樣的情況下，time complexity 是 O(1)。我們在函式內使用的變數是有限的，space complexity 是 O(1)。 若是字串的長度沒有限制，遍歷整個字串後，時間複雜度會是 O(n)。 Time Complexity: O(1); Space Complexity: O(1) <li>Right-to-Left pass + hash table</li> 上述的第一種作法會導致很多的 if-else，如果適當地使用 hash table 則可大幅縮減函數的運算時間。我們利用 hast table 把羅馬字母與整數的對應 pairs 儲存起來。然後將字串最右側的字元對應的整數值先存入我們的 return number 中，這樣剩餘的每個字元右側都有一個字元。然後，我們從字串右側的第二個元素遍歷到字串的左邊。如果 s[i] < s[i+1]，則減掉 s[i]；否則，就加上 s[i]。 Time complexity 同上面的分析。Space complexity 因為羅馬字母的數目是有限的，所以 hash table 的大小也是固定的，故記憶體成本為常數。 Time Complexity: O(1); Space Complexity: O(1) </ul> <li>測試</li> <ul> <li>test 1</li> Input: s = "MCDIX" ; Output: 1409 <li>test 2( worst case )</li> Input: s = "MMMDCCCLXXXVIII" ; Output: 3888 字串長度達到 constraints 內的最長長度。 <li>empty string or the string with the wrong characters( edge case )</li> 如果 input 是空字串或是出現規範羅馬字母以外的字母，比如出現字母 T，這時候函式應該先遍歷一次字串對 input 檢查是否合法，如果格式不合法就印出錯誤訊息。如果字元都合法才開始正式計算數字。 </ul> </ol>