Lesson learned: Do it right the first time 🙂

Name: Roman to Integer
Difficulty: Easy
Description: Convert a Roman Numeral to an Integer

Example:

Given III, return 3
Given MCMXCIV, return 1994

I was a little lazy on this one, this was the third for the evening and my brain was checking out. I chose to replace the cases where subtraction was found, for example IV is 4, with a symbol associated with the value. I then iterated over the string and looked up the character value in a map, adding it to the total.

Actually, I was a bit upset with such an inefficient solution, so I submitted another solution. Here is the first solution which was slow and used too much memory, followed by the second solution. It is interesting to compare the two solutions to see the difference in resource usage.

class Solution {
private:
    map<char, int> values = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000},
            {'@', 4},
            {'#', 9},
            {'$', 40},
            {'_', 90},
            {'%', 400},
            {'&', 900}
    };

    map<string, string> temps = {
            {"IV", "@"}, // 4
            {"IX", "#"}, // 9
            {"XL", "$"}, // 40
            {"XC", "_"}, // 90
            {"CD", "%"}, // 400
            {"CM", "&"}  // 900
    };

public:
    int romanToInt(string s) {
        for(auto const& [key, val] : temps) {
            s = regex_replace(s, regex(key), val);
        }

        int total = 0;

        for (char ch : s) {
            auto it = values.find(ch);
            if (it == values.end()) return 0;
            total += it->second;
        }

        return total;
    }
};

Here is my second submission, it is much more efficient, as you can see from the results:

I simply iterate over the string, peeking ahead when necessary, and maintaining a running total.

class Solution {
public:
    int romanToInt(string s) {
        if (s.empty() || s.length() > 15) return 0;

        int total = 0;

        auto j = s.begin();

        for (auto i = s.begin(); i != s.end(); ++i) {
            j = i + 1;

            if (*i == 'I') {
                if (*j == 'V') {
                    total += 4;
                    ++i;
                } else if (*j == 'X') {
                    total += 9;
                    ++i;
                } else {
                    total += 1;
                }

                continue;
            }

            if (*i == 'X') {
                if (*j == 'L') {
                    total += 40;
                    ++i;
                } else if (*j == 'C') {
                    total += 90;
                    ++i;
                } else {
                    total += 10;
                }

                continue;
            }

            if (*i == 'C') {
                if (*j == 'D') {
                    total += 400;
                    ++i;
                } else if (*j == 'M') {
                    total += 900;
                    ++i;
                } else {
                    total += 100;
                }

                continue;
            }

            switch (*i) {
                case 'V': total += 5; break;
                case 'L': total += 50; break;
                case 'D': total += 500; break;
                case 'M': total += 1000; break;
                default:
                    return 0; // unknown value
            }
        }

        return total;
    }
};