【LittleDuck_LeetCodeNote】13 - Roman to Integer

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。

Question and Hints

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:

• 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
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].

First Solution

💡 用switch-case從第一個字母開始找，
用對應的文字找出這一輪對應的的Index，記錄為nowIndex，
因為羅馬數字有將小字母擺在大字母左邊表示相減的特性，
所以檢查上一個字母(lastIndex)是否小於nowIndex，
如果是，就先相減，再做相加，
如果不是就直接加。

class Solution {
    public int romanToInt(String s) {
        char[] RomanNumber = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        int[] RomanValue = {1, 5, 10, 50, 100, 500, 1000};
        int lastIndex = 0, nowIndex = 0, result = 0;

        for(int i=0; i < s.length(); i++){
            switch(s.charAt(i)){
                case 'I':
                    nowIndex = 0;
                    break;
                case 'V':
                    nowIndex = 1;
                    break;
                case 'X':
                    nowIndex = 2;
                    break;
                case 'L':
                    nowIndex = 3;
                    break;
                case 'C':
                    nowIndex = 4;
                    break;
                case 'D':
                    nowIndex = 5;
                    break;
                case 'M':
                    nowIndex = 6;
                    break;
            }
            if(i == 0)
                lastIndex = nowIndex;
            if(lastIndex < nowIndex){
                result -= RomanValue[lastIndex] * 2;
            }
            result += RomanValue[nowIndex];
            lastIndex = nowIndex;
        }

        return result;
    }
}

⏰ Runtime: 4 ms (95.38 %)

📦 Memory: 42.8 MB (57.74 %)

Upgrade Solution

more clear.

💡 First Solution邏輯大致上對了，但可以改得更精簡， 並且，順序反過來會更好找。

• 不用2個陣列，而是直接在switch-case完成羅馬數字的參照轉換(透過number)
• 因為不用陣列，所以不用Index，而是直接用字母代表的數字進行比較。
• 「小字母擺在大字母左邊表示相減的特性」從數學角度來看，即當由右往左看時，下一個數字如果比較小，就要進行相減，比起原本相減2次更直觀。
• JDK14更新了switch-case的寫法，改用 -> 取代 : ，且結尾不用再寫break。

class Solution {
    public int romanToInt(String s) {
        int answer = 0, number = 0, prev = 0;

        for (int j = s.length()-1; j >= 0; j--) {
            switch (s.charAt(j)) {
                case 'M' -> number = 1000;
                case 'D' -> number = 500;
                case 'C' -> number = 100;
                case 'L' -> number = 50;
                case 'X' -> number = 10;
                case 'V' -> number = 5;
                case 'I' -> number = 1;
            }
            if (number < prev)
                answer -= number;
            else
                answer += number;
            prev = number;
        }
        return answer;
    }
}

⏰ Runtime: 3 ms (100 %)

📦 Memory: 42.9 MB (57.74 %)

Bonus Solution

Use Hashtable to store Roman numbers.

💡 與First Solution的邏輯相同，差別在於用Hashtable替代兩個陣列，
結果來看明顯比較慢，
其實兩個陣列的搜尋方式就跟Hashtable的道理是一樣的，
只是把key跟value寫出來，
並且中間沒有Hash function轉換，
所以兩個陣列反而比較快，
但HashTable還是有安全性上的優點。

class Solution {
    public int romanToInt(String s) {
        Map<Character,Integer>map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        
        int value=0;
        char prevVal = 'I';
        for(int i=s.length()-1; i>=0; i--){
            char nowVal = s.charAt(i);
            if(map.get(nowVal) < map.get(prevVal))
                value -= map.get(nowVal);
            else
                value += map.get(nowVal);
            prevVal = nowVal;
        }
        return value;
    }
}

⏰ Runtime: 7 ms (35.9 %)

📦 Memory: 42.6 MB (82.32 %)