Roman to Integer

Problem: Roman to Integer

The definition of Roman numerals can be found on Wikipedia. Due to this reference, we only do two kind of operations on a single character. We will add or subtract corresponding numbers. Note that we won't use continuous repeating character to represent a number need to be subtracted, that is, we use "III" to represent 3 instead of "IIV".

We can scan through the string and justify whether we want to add or minus based on the following character. To make the solution simpler, we can reverse the string to check following letter as previous one.

Code in Python:

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        dict = ({'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000})
        prev, res = 0, 0
        for c in s[::-1]:
            cur = dict[c]
            if cur < prev:
                res -= cur
            else:
                res += cur
            prev = cur
        return res

If we read the Roman numbers from left to right, a trivial way is every time we read a character we also read its following one.

Code in Java:

public class Solution {
    public int romanToInt(String s) {
        int res = 0;
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        hm.put('I', 1);
        hm.put('V', 5);
        hm.put('X', 10);
        hm.put('L', 50);
        hm.put('C', 100);
        hm.put('D', 500);
        hm.put('M', 1000);

        int i = 0;
        while (i < s.length()) {
            if (i < s.length()-1) {
                int current = hm.get(s.charAt(i));
                int next = hm.get(s.charAt(i+1));
                if (current < next) {
                    res += next-current;
                    i += 2;
                } else {
                    res += current;
                    i++;
                }
            } else {
                int current = hm.get(s.charAt(i));
                res += current;
                i++;
            }
        }

        return res;
    }
}

A quicker left to right solution can be found here.