[LeetCode] Roman to Integer

Given a roman numeral, convert it to an integer.

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

思路：

Integer to Roman那题的follow up。关键还是解决例如IV = 4的subtractive notation的情况。可以用与Integer to Roman那题一样的思路扩展罗马字符到字符组合：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int romanToInt(string s) { string dict[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; int num[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1}; int i=0, index=0, ret=0; while(i<s.size() && index<13) { string target = dict[index]; string cur = s.substr(i,target.size()); if(cur==target) { ret += num[index]; i += target.size(); } else { index++; } } return ret; } };

更简洁清楚的解法：
找下subtractive notation的规律，以简单的例子s = IX 说明。
1. 如果按照additive性质的话应该ret = 1+10 = 11。但因为num(X)=10>num(I)=1，ret = 10 - 1。
2. 将subtractive rule转换成等效的additive rule：ret = 1 + (10 - 2*1)

建立一个罗马字符对应整数的hash table ht。
当ht[s[i]] > ht[s[i-1]]，即为subtractive nontation：ret += (ht[s[i]] - 2*ht[s[i-1]])
否则为additive nontation：ret+=ht[s[i]]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: int romanToInt(string s) { if(s.empty()) return 0; unordered_map<char,int> ht({{'I',1}, {'V',5}, {'X',10}, {'L',50}, {'C',100}, {'D',500}, {'M',1000}}); int ret = 0; for(int i=0; i<s.size(); i++) { if(ht.count(s[i])==0) return 0; ret += ht[s[i]]; if(i!=0 && ht[s[i]]>ht[s[i-1]]) ret -= 2*ht[s[i-1]]; } return ret; } };