HashMaps, Roman Numerals, & You: A Simple Coding Challenge

The Problem

The task was simple. Given a string representing a roman numeral, convert it to an integer.

I had a prior understanding of Roman numerals and their formatting, so I was prepared to jump straight into it, but as I would soon find out, even simplistic challenges like this one are not to be underestimated.

Constraints

I had initially ignored the constraints of the problem and tried to approach it with as wide a lens as possible. This instinct came from my experience creating games with Unity and C#, where null references and out-of-bounds exceptions can cause a crucial game object to stop working. However, these constraints would later prove to be integral to solving the problem in a clean, optimized way.

Attempt #1 — Clumsy Beginnings

class Solution {
    public int romanToInt(String s) {
        int result = 0;
        // ???
        return result;
    }
}

I would need to pull each letter of the string and find its corresponding integer value. The obvious first step was to create a for-loop, but when thinking of what exactly should be done within that loop, suddenly the best solution was not so easy to find.

for(int i = 0; i < s.length(); i++)
{
    switch(s.charAt(i))
    {
        case 'I':
            result += 1;
            break;
        case 'V':
            result += 5;
            break;
        case 'X':
            result += 10;
            break;
        case 'L':
            result += 50;
            break;
        case 'C':
            result += 100;
            break;
        case 'D':
            result += 500;
            break;
        case 'M':
            result += 1000;
            break;
    }
}

A switch statement like this could potentially work, but this block alone is already more headache than it’s worth, and reading through each possible letter at every stage of the for-loop is not the most optimized plan.

I knew there was a better way to approach this. I needed a data structure in which I could store characters paired with corresponding integers. Arrays, lists, and other one-dimensional structures wouldn’t cut it. Even if I did use them to devise a solution, the program’s optimization would greatly suffer.

Attempt #2 — Enter The HashMap

With a HashMap, I could store these letter-number pairings and pull from them during the central for-loop. Since doing so was as simple as calling the get() method, I could do it without substantially increasing the complexity of the overall program. First, I would need to declare the map and fill it with the appropriate pairings.

class Solution {
    static Map<Character, Integer> RomanNumerals = new HashMap<Character, Integer>();

    public int romanToInt(String s) {
        // BUILD ROMAN NUMERAL HASHMAP
        RomanNumerals.put('I', 1);
        RomanNumerals.put('V', 5);
        RomanNumerals.put('X', 10);
        RomanNumerals.put('L', 50);
        RomanNumerals.put('C', 100);
        RomanNumerals.put('D', 500);
        RomanNumerals.put('M', 1000);
        // INITIALIZE RESULT TO ZERO
        int result = 0;

        // LOOP THROUGH THE STRING
        for(int i = 0; i < s.length(); i++)
        {
            // ADD INT EQUIVALENT TO CHARACTER FROM HASHMAP
            // ONLY IF CHARACTER IS PRESENT IN MAP
            if(RomanNumerals.containsKey(s.charAt(i)))
                result += RomanNumerals.get(s.charAt(i)); 
        }

        return result;
    }
}

The body of the for-loop came easily after that.

Easy-peasy, right? The code is clean, readable, and demonstrably error-free. After running the test cases, however, I realized that I wasn’t finished just yet.

My code had failed the third test case. It surprised me at first. I wondered; if the function worked properly for the first two test cases, what was the issue with the third? Then I took a closer look at the input string: “MCMXCIV”.

The first two test strings, “III” and “LVIII”, had characters organized in such a way that each one corresponded to a greater integer than the next. As such, each integer could be added to the result with no headache. This third string was different, though.

If a roman numeral comes before another one with a larger value, it subtracts from that next value. With our current method, a sequence like “CM”, which should correspond to 900, becomes 1100, which throws off our result. The same is true for “XC” later in the string, which was converted to 110 as part of this solution when it should have been converted to 90.

I had to account for this in my next solution in order to pass the third test case, but how was I to do it? On the surface, the change to be made was clear. When going through the loop, if the next letter of the string following the current one corresponded to a larger integer from the HashMap, the number corresponding to the current letter would be subtracted from the total rather than added.

I thought about the mess that would be made if I took several lines to check if the current character was the last in the string, check if the next existed within the HashMap, and check if its corresponding integer was larger than the current one in the loop, all in service of what should be a relatively simple if-else statement.

for(int i = 0; i < s.length(); i++)
    {
        if(i < s.length() - 1 
            && RomanNumerals.containsKey(s.charAt(i))
                && RomanNumerals.get(s.charAt(i + 1)) > RomanNumerals.get(s.charAt(i)))
                    result -= RomanNumerals.get(s.charAt(i));
        else result += RomanNumerals.get(s.charAt(i));
    }

Needless to say, I didn’t like how it looked. I wanted a solution that was cleaner and more concise, even if not by much.

This was the point at which I remembered the constraints of the problem. According to these constraints, the string input was guaranteed to be a valid Roman numeral and contain only the alphabetical characters. I didn’t have to check if the character existed or if it was present in the HashMap; according to the boundaries of the problem, they would be there as long as the map itself was declared correctly.

Attempt #3 — Clean Subtraction

class Solution {
    static Map<Character, Integer> RomanNumerals = new HashMap<Character, Integer>();

    public int romanToInt(String s) {
        // BUILD ROMAN NUMERAL HASHMAP
        RomanNumerals.put('I', 1);
        RomanNumerals.put('V', 5);
        RomanNumerals.put('X', 10);
        RomanNumerals.put('L', 50);
        RomanNumerals.put('C', 100);
        RomanNumerals.put('D', 500);
        RomanNumerals.put('M', 1000);
        // INITIALIZE RESULT TO ZERO
        int result = 0;

        for(int i = 0; i < s.length(); i++)
        {
            // SUBTRACT INT EQUIVALENT TO CHARACTER FROM HASHMAP IF THE NEXT
            // CHARACTER HAS A HIGHER VALUE
            if(i < s.length() - 1 && 
                RomanNumerals.get(s.charAt(i + 1)) > RomanNumerals.get(s.charAt(i)))
                result -= RomanNumerals.get(s.charAt(i));
            else result += RomanNumerals.get(s.charAt(i));
            // OTHERWISE ADD INT EQUIVALENT TO CHARACTER FROM HASHMAP
        }

        return result;
    }
}

After erasing the containsKey() statement, only the essential instructions remained. The integer value would be added to the result variable unless that integer was smaller than the next, and since that check cannot be made for the last character of the string, we must still ensure the checked character is not the last.

With the final test case passed, the challenge is complete!