Interview Classic 150 Questions P13 Roman to Integer

---

Timeline

timeline

2025-11-09

init

simulation, hash table

---

Title:

P13 Roman to Integer

https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150

Just simulate directly

#include <string>
#include <unordered_map>
#include <queue>

using std::unordered_map;
using std::string;
using std::queue;

class Solution {
    private:
	unordered_map<string, int> roman_alpha_to_int;

    public:
	Solution()
	{
		roman_alpha_to_int = { { "I", 1 },   { "V", 5 },   { "X", 10 },	 { "L", 50 },	{ "IV", 4 },
				       { "IX", 9 },  { "XL", 40 }, { "XC", 90 }, { "CD", 400 }, { "CM", 900 },
				       { "C", 100 }, { "D", 500 }, { "M", 1000 } };
	}
	int romanToInt(string s)
	{
		queue<char> ch_que;
		int res = 0;
		char front, next;

		for (char ch : s) {
			ch_que.push(ch);
		}

		while (!ch_que.empty()) {
			front = ch_que.front();
			ch_que.pop();
			string tmp;
			tmp.push_back(front);
			if (!ch_que.empty()) {
				next = ch_que.front();
				tmp.push_back(next);
				if (!roman_alpha_to_int.count(tmp)) {
					tmp.pop_back();
				} else {
					ch_que.pop();
				}
			}
			res += roman_alpha_to_int[tmp];
		}
		return res;
	}
};
int main()
{
	Solution S;
	string s = "III";
	S.romanToInt(s);
}

The above method using string hash is not efficient, you can simulate directly:

class Solution {
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

public:
    int romanToInt(string s) {
        int ans = 0, value;
        int n = s.length();
	
        for (int i = 0; i < n; ++i) {
            value = symbolValues[s[i]];
            
	    if (i < n - 1 && value < symbolValues[s[i + 1]])
                ans -= value;
            else
                ans += value;
        }
        return ans;
    }
};