One of the leecode problem quotes Roman Numberal. Out of curiosity, I query some document about Roman Numberal, wikipedia and Roman Numerals Chart

About Roman Numberal

Roman numerals consists of seven chars with the following mapping relationship:

I => 1
V => 5
X => 10
L => 50
C => 100
D => 500
M => 1000

A legal Roman Numberal obeys the simple principle. This is how I remember it. Larger char appears firstly and there are at most three continuous chars. Thus, VIII equals 8, however, VIIII is wrong. The correct form of 9 is IX whihc means X minus I. Therefore, when a smaller char before a larger char, it means right minus left. Such as, IX equals X(10) - I(1) = 9. A more complicated one, LXXXIX means L(50) + X(10)*3 + X(10) - I(1) = 89.

CPP implementation

Based on the previous principle, I wrote a simple program to convert Roman Numberals to integers. At first, I use the unordered_map in STL to deal with the mappings, the problem costs 72ms on leetcode OJ. When I give up unordered_map and use basic switch case method, it costs only 36ms which is half the time with unordered_map. Although I haven’t do more experiments on the efficiency between switch and unordered_map, it can be seen easily that using unordered_map may cost too much resource. When the dataset is quite small, it’s better to choose switch case.

Here is my simple code:

class Solution {
public:
    int romanToInt(string s) {
        int sum = 0;
        int size = s.size();
        for(int i=0;i<size;i++){
            if (i!=size-1 && romanCharToInt(s[i]) < romanCharToInt(s[i+1])){
                sum -= romanCharToInt(s[i]);
            } else {
                sum += romanCharToInt(s[i]);
            }
        }
        return sum; 
    }
private:
    int romanCharToInt(char v){
        switch (v){
            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;
        }
        return 0;
    }
};