class Solution { private: const static char* pattern[]; const static char* roman[]; unordered_map<string, int> a2i; public: int romanToInt(string s) { int res = 0; if (a2i.size() == 0) build_tlb(); while (!s.empty()) { int len = s.length(); for (int i=min(4, len); i>0; i--) { unordered_map<string, int>::iterator iter = a2i.find(s.substr(len-i)); if (iter == a2i.end()) continue; res += iter->second; s.resize(len - i); break; } } return res; } void build_tlb() { int pw = 1; for (int i=0; i<3; i++) { for (int j=1; j<=9; j++) { string rm; for (int k=0; pattern[j][k] != ‘\0‘; k++) { rm.push_back(roman[i][ pattern[j][k] - ‘0‘ ]); } a2i.insert(make_pair(rm, pw * j)); } pw *= 10; } a2i.insert(make_pair("M", 1000)); a2i.insert(make_pair("MM", 2000)); a2i.insert(make_pair("MMMM", 3000)); } }; const char* Solution::pattern[] = {"A", "0", "00", "000", "01", "1", "10", "100", "1000", "02"}; const char* Solution::roman[] = {"IVX", "XLC", "CDM", "M"};
580ms+,时间有点长
仔细观察罗马数字的话,可以把每个字母直接由一个数值替代,然后将他们累加,不过有个例外就是遇到4,9时要看字母前面一个字母的数值比如IV如果小于后面的则实际对应值为V-I = 5-1 = 4,X - I= 10 - 1 = 9
具体可以参考:http://www.cnblogs.com/zhuli19901106/p/3453180.html
LeetCode Roman to Integer,布布扣,bubuko.com
原文:http://www.cnblogs.com/lailailai/p/3857276.html