Leetcode 13 Solution

This article provides solution to leetcode question 13 (roman-to-integer)


Thinking Process

This question is the reverse process of integer-to-roman. We should leverage the similar technique, i.e., using the modified symbol table.

To convert the roman string to integer, we’ll just need to grab each symbol from the list and add them into the integer.

Time & Space Complexity

Assuming N is the length of the input string

  • Time complexity: O(n)
  • Space complexity: O(1)


class Solution {
    int romanToInt(string s) {
        vector<pair<int, string>> a;
        a.push_back(make_pair(900, "CM"));
        a.push_back(make_pair(400, "CD"));
        a.push_back(make_pair(90, "XC"));
        a.push_back(make_pair(40, "XL"));
        a.push_back(make_pair(9, "IX"));
        a.push_back(make_pair(4, "IV"));
        a.push_back(make_pair(1000, "M"));
        a.push_back(make_pair(500, "D"));
        a.push_back(make_pair(100, "C"));
        a.push_back(make_pair(50, "L"));
        a.push_back(make_pair(10, "X"));
        a.push_back(make_pair(5, "V"));
        a.push_back(make_pair(1, "I"));

        int i = 0;
        int res = 0;
        while (i < s.size())
            for (int j = 0; j < a.size(); j++)
                if (s.substr(i, a[j].second.size()) == a[j].second)
                    res += a[j].first;
                    i += a[j].second.size();
        return res;