罗马数字转整数：识别特殊减法对

罗马数字通常从左到右累加；IV、IX、XL、XC、CD、CM 是需要整体处理的减法组合。代码用一个单字符映射和一个双字符映射分别处理它们。

1
class Solution {
2
public:
3
    int romanToInt(string s) {
4
        map<char, int> m = {
5
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
6
            {'C', 100}, {'D', 500}, {'M', 1000}
7
        };
8

9
        map<string, int> n = {
10
            {"IV", 4}, {"IX", 9},
11
            {"XL", 40}, {"XC", 90},
12
            {"CD", 400}, {"CM", 900}
13
        };
14

15
        int res = 0;
16

17
        for(int i = 0; i < s.size(); i ++ ) {
18
            if(i + 1 < s.size()) {
19
                string t = s.substr(i, 2);
20
                if(n.count(t)) {
21
                    res += n[t];
22
                    i ++;
23
                    continue;
24
                }
25
            }
26
            res += m[s[i]];
27
        }
28

29
        return res;
30
    }
31
};

复杂度#

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ ；符号映射大小固定。

判断条件
不必逐一枚举 IV、IX 等减法组合。比较当前字符与下一个字符，就能统一覆盖全部合法减法对。