Romans to Integer

When you go to Rome… Learn Roman numbers.

On my second day doing leetcode, I did convert Roman numbers to integer values. The problem was, provided a string of Roman numbers, convert them to an integer. Below is a leetcode screenshot of the problem definition.

Leetcode

Thought Process

This was not as straight forward as the previous problem I attempted. However, I figured if I can present the provided table as a Map, and loop through the provided string to check if it matches a key in the map that would be a good starting point. While looping, I opted to go right to left as it is mentioned that roman numbers are written left to right. This would allow me to handle the subtraction.

My code

int romanToInt(String s) {
    
    final romanMap = {
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000
    };

    //prev handles the comparison numeral && total holds the running sum
    int prev = 0, total = 0;

    //loop from right to left
    for(int i = s.length - 1; i >=0; i--){
        //get the last character
        String char = s[i];
        //look up integer value
        int value = romanMap[char] ?? 0;
        //perform subtraction if current value is greater than prev otherwise add
        if(value < prev){
            total -= value;
        }else{
            total += value;
        }

    //update previous value
    prev = value;

    }

    //returns the integer equivalent
    return total;
 }

This solution was better than 78% of solutions, which is a huge improvement from the previous one. It took 9ms to run. The ideal code took 1ms.

Get Arthur Pundo’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Ideal Code

int romanToInt(String s) {
    int ans = 0, num = 0;
        for (int i = s.length-1; i >= 0; i--) {
            switch(s[i]) {
                case 'I': num = 1; break;
                case 'V': num = 5; break;
                case 'X': num = 10; break;
                case 'L': num = 50; break;
                case 'C': num = 100; break;
                case 'D': num = 500; break;
                case 'M': num = 1000; break;
            }
            if (4*num < ans) ans-=num;
            else ans+=num;
        }
        return ans;
  }

The notable difference is the use of switch case to check for the integer equivalent of a roman number. Additionally, the subtraction is cleverly handled:

if (4*num < ans) ans-=num;
            else ans+=num;

If num is small and we have already added something 4x larger (ans >4 * num), its likely a subtractive case.
What this means is:

for 'IV', num = 1, ans = 5 → 4*num < ans → subtract 1 → result = 4.

Otherwise add as usual.

Conclusion

This did not seem achievable when I first looked at it but I ended up doing it, better nonetheless. I was pretty happy with how fast it ran. Looking forward to the next challenge.