【LittleDuck_LeetCodeNote】13 - Roman to Integer

Question and Hints

Symbol        Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

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

Input: s = "III"
Output: 3
Explanation: III = 3.

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

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

• 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;
    }
}

Upgrade Solution

💡 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;
    }
}

Bonus Solution

💡 與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;
    }
}