What you need to know about Leetcode’s Convert Roman to Integer. My thought process as a beginner.

This is a Leetcode Problem where we have to convert a Roman numeral into an integer e.g “III” will give you 3, “IV” will give you 4, “MCMXCIV” will give 1994. As you can see, the input is a String.

problem description

FIRST APPROACH

My first approach was to add the Symbol and Value to a map. This was to enable faster look up time(which happens in constant time O(1)). Then I thought about the problem and came up with this algorithm:

1. Add the Symbol and Value to a map as stated above;
2. loop through the length of the string input;
3. for each character of the string, get the corresponding value from the map;
4. check if it matches any of the three conditions (I,X,C which corresponds to 1, 10 and 100 respectively).
5. if it does not, just add the value from the map to a global accumulator and increment the global counter by 1;
6. if it does, get the value of the next character in the string and check if it matches with any of the conditions attached to I,X,C. if it does, subtract it from the value from the third step above and add to global variable (total). If it doesn’t, just add the current character value to the global accumulator.

MY CODE

public static   int romanToInt(String s) {
    HashMap<Character, Integer> KeyValues = new HashMap<>();
    KeyValues.put('I', 1);
    KeyValues.put('V', 5);
    KeyValues.put('X', 10);
    KeyValues.put('L', 50);
    KeyValues.put('C', 100);
    KeyValues.put('D', 500);
    KeyValues.put('M', 1000);
    int count = 0;
    int length = s.length();
    int total = 0;
    while ( count < length) {
        //get character  from map
        int lookUp = KeyValues.get(s.charAt(count));
        if (lookUp == 1) { //if it is I
            int checker = 0;
            //prevent null pointers
            if (count+1 < s.length())
                //get the value of the next character
                checker = KeyValues.get(s.charAt(count + 1));
            //first condition if I: I comes before V and X
            if ((checker == 5 || checker == 10)) {
                //just subtract from the previous character
                total += checker - lookUp;
                //increment the counter by 2 to pick character
                count += 2;
            }else {
                //if the value is not in the map, just add
                // the current character value to the total variable
                total += lookUp;
                count ++; //just move one step
            }
        } else if (lookUp == 10) {
            int checker = 0;
            if (count+1 < s.length())
                checker = KeyValues.get(s.charAt(count + 1));
            if ((checker == 50 || checker == 100)) {
                total += checker - lookUp;
                count += 2;
            }else {
                total += lookUp;
                count ++;
            }
        } else if (lookUp == 100) {
            int checker = 0;
            if (count+1 < s.length())
                checker = KeyValues.get(s.charAt(count + 1));
            if ((checker == 500 || checker == 1000)) {
                total += checker - lookUp;
                count += 2;
            }else {
                total += lookUp;
                count ++;
            }
        }else {
            total += lookUp;
            count++;
        }
    }
    return total;
}

OUTCOME

Turned out the algorithm worked( 🕺 🕺 🕺) except some nullpointers which I checked as shown in the code above. The outcome is shown below:

From the image above you can see the my solution was really slow. I found out it was because I was printing out in multiple places (debugging). so I removed the print statements and got this:

faster solution.

wow( 😧 😧 😧). I never know print statements could slow down the running time.

IMPROVEMENT

I tried various ways to make it run better than 49% but couldnt find a way. My memory usage was very good just the running time. So i eventually resorted to checking other people’s solutions on the discuss section. It turned out most of the solutions had the same concept and had similar run time but I found a solution than ran in 3ms ( 😧 😧 😧):

public int romanToInt(String s) {
        int num = 0;
        int l = s.length();
        int last = 1000;
        for (int i = 0; i < l; i++){
            int v = getValue(s.charAt(i));
            if (v > last) num = num - last * 2;
            num = num + v;
            last = v;
        }
        return num;
    }
    private int getValue(char c){
        switch(c){
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return 0;
        }
    }

I think I still need a thorough explanation from you guys of how he/she came up with this superb solution.

LESSONS

1. I learnt to remove all print statements before submitting my solutions.
2. checking null pointers for char values.

CONCLUSION

Thank you so much guys and I hope you drop a comment