[Leetcode] 13. Roman to Integer 解题报告

题目：

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

思路：

可以看作是Leetcode 12的孪生题目，但是难度却比上一道题目低不少。通过上一道题目的分析可知，在该题目中只需要判断罗马数字中的每一个字符是否大于等于其后一个字符，如果是，则它对最终整数的贡献是正的，否则贡献就是负的。线性扫描即可在O(n)的时间复杂度内解决问题，其中n是罗马字符的长度。

代码：

class Solution {
public:
    int romanToInt(string s) {
        int length = s.length();
        if(length == 0)
            return 0;
        
        std::unordered_map dict;
        dict['I'] = 1;
        dict['V'] = 5;
        dict['X'] = 10;
        dict['L'] = 50;
        dict['C'] = 100;
        dict['D'] = 500;
        dict['M'] = 1000;
    
    	int result = 0, value = 0;
    	for (int i = 0; i < length - 1; i++)
    	{
    		value = dict[s[i]];
    		if (value < dict[s[i + 1]])     // value should be subtracted
    		    result -= value;
    		else                            // value should be added
    			result += value;
    	}
    	result += dict[s[length - 1]];
    	return result;
    }
};

如果所给的罗马字符不一定合法呢？如何判断？（这是我自己想出来的follow up）。但是感觉该Follow up的意义也不是很大。如果非要回答，可以参考上一题目中给出的计数规则和组合规则，逐条判断所给字符串是否合法。