[📝LeetCode #13] Roman to Integer

#leetcode #100daysofcode #hashmap #java

🎀 The Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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.

👩‍💻 My Answer

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int i;

        for (i = 0; i < s.length() - 1; i++) {
            char letter = s.charAt(i);

            if (letter == 'M')
                sum += 1000;
            else if (letter == 'D')
                sum += 500;
            else if (letter == 'C' && s.charAt(i+1) == 'D') {
                sum += 400;
                i++;
            }
            else if (letter == 'C' && s.charAt(i+1) == 'M') {
                sum += 900;
                i++;
            }
            else if (letter == 'C')
                sum += 100;
            else if (letter == 'L')
                sum += 50;
            else if (letter == 'X' && s.charAt(i+1) == 'C') {
                sum += 90;
                i++;
            }
            else if (letter == 'X' && s.charAt(i+1) == 'L') {
                sum += 40;
                i++;
            }
            else if (letter == 'X')
                sum += 10;
            else if (letter == 'V')
                sum += 5;
            else if (letter == 'I' && s.charAt(i+1) == 'X') {
                sum += 9;
                i++;
            }
            else if (letter == 'I' && s.charAt(i+1) == 'V') {
                sum += 4;
                i++;
            }
            else if (letter == 'I')
                sum += 1;
        }

        if (i == s.length() - 1) {
            char letter = s.charAt(i);
            if (letter == 'M')
                sum += 1000;
            else if (letter == 'D')
                sum += 500;
            else if (letter == 'C')
                sum += 100;
            else if (letter == 'L')
                sum += 50;
            else if (letter == 'X')
                sum += 10;
            else if (letter == 'V')
                sum += 5;
            else if (letter == 'I')
                sum += 1;
        }

        return sum;
    }
}

Pro & Con

✅ Runtime
✖️ Too long
✖️ Bit complicated (Hard to read)

💋 Ideal Answer

Approach - "HashMap"

I used the charAt and if statement to go through the array. But, I read the solution on LeetCode and they used the HashMap.

New Code

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 sum = 0;

        for (int i = 0; i < s.length(); i++) {
            if (i == s.length() - 1) {
                sum += map.get(s.charAt(i));
                break;
            }

            int current = map.get(s.charAt(i));
            int next = map.get(s.charAt(i+1));

            if (current >= next)
                sum += current;
            else {
                sum += next - current;
                i++;
            }
        }

        return sum;
    }
}

It still beats 55%, not 100%. So, I checked and saw the ideal code on LeetCode. Here is:

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> m = new HashMap<>();

        m.put('I', 1);
        m.put('V', 5);
        m.put('X', 10);
        m.put('L', 50);
        m.put('C', 100);
        m.put('D', 500);
        m.put('M', 1000);

        int ans = 0;

        for (int i = 0; i < s.length(); i++) {
            if (i < s.length() - 1 && m.get(s.charAt(i)) < m.get(s.charAt(i + 1))) {
                ans -= m.get(s.charAt(i));
            } else {
                ans += m.get(s.charAt(i));
            }
        }

        return ans;
    }
}

WAITTTT! I ran the "BEST" code, and it still DOES NOT beat 100%. (This was almost the same as my New Code.) So, I searched more and I think using switch condition is the best for Java, and the code below actually beat 100% (I ran!):

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

💡 What I Learned

How to use HashMap

Map<>() map = new HashMap();
map.put(KEY, VALUE);
map.get(KEY);

Use '' for char and "" for array
There are many FAKE solution posts on LeetCode.

DEV Community