Roman to Integer

Difficulty: Easy

Tags: Hash Map, String

Constraints: 1 ≤ |s| ≤ 15

Problem

Given a Roman numeral string s, convert it to an integer. Subtractive pairs like IV, IX, XL, XC, CD, CM are allowed.

Constraints: 1 <= s.length <= 15, characters are in {I, V, X, L, C, D, M}.

Approach

Map each Roman character to its integer value.
Scan left to right; if current value is less than the next, subtract, else add.

Step-by-step

#include <string>
using namespace std;

#include <string>: enables use of std::string.
using namespace std;: avoids writing std:: repeatedly.

class Solution {
public:
    int romanToInt(const string& s) {

class Solution: LeetCode convention.
public: make the method accessible for tests.
const string& s: pass by const reference to avoid copying.

        static int values[256] = {0};
        static bool initialized = false;
        if (!initialized) {
            values['I'] = 1;
            values['V'] = 5;
            values['X'] = 10;
            values['L'] = 50;
            values['C'] = 100;
            values['D'] = 500;
            values['M'] = 1000;
            initialized = true;
        }

values[256]: O(1) ASCII lookup table (256 possible char values).
Initialize once using an initialized flag.
Map Roman numerals to their integer values.

        int total = 0;
        for (size_t i = 0; i < s.size(); i++) {
            int val = values[(unsigned char)s[i]];
            int next = (i + 1 < s.size()) ? values[(unsigned char)s[i+1]] : 0;
            total += (val < next) ? -val : val;
        }
        return total;
    }
};

val and next: current and next numeral values.
Rule: if current < next, subtract; else add.
Time: O(n); Space: O(1).

Full Solution (C++)

#include <string>
using namespace std;

class Solution {
public:
    int romanToInt(const string& s) {
        static int values[256] = {0};
        static bool initialized = false;
        if (!initialized) {
            values['I'] = 1;
            values['V'] = 5;
            values['X'] = 10;
            values['L'] = 50;
            values['C'] = 100;
            values['D'] = 500;
            values['M'] = 1000;
            initialized = true;
        }

        int total = 0;
        for (size_t i = 0; i < s.size(); i++) {
            int val = values[(unsigned char)s[i]];
            int next = (i+1 < s.size()) ? values[(unsigned char)s[i+1]] : 0;
            total += (val < next) ? -val : val;
        }
        return total;
    }
};