Leetcode – Roman to Integer

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;
    }
};

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s