Leetcode 13 Solution

This article provides solution to leetcode question 13 (roman-to-integer)
Categories:
Tags:
Access this page by simply typing in "lcs 13" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/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)

Solution

class Solution {
public:
    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();
                    break;
                }
            }
        }
        return res;
    }
};