Description:
https://leetcode.com/problems/roman-to-integer/#/description
Boundary:
s.size() = 0
Algorithm:
Use unordered_map m<char, int> to construct the correspondence between character and number like:
| character | numerical value |
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Then check the string s one by one
if m[s[i]] < m[s[i+1]] result -= m[s[i]]
else result += m[s[i]]
Code:
class Solution {
public:
int romanToInt(string s) {
if (s.size() == 0) return 0;
m[‘I’] = 1;
m[‘V’] = 5;
m[‘X’] = 10;
m[‘L’] = 50;
m[‘C’] = 100;
m[‘D’] = 500;
m[‘M’] = 1000;
int result = 0;
for (int i = 0; i < s.size() – 1; i++)
{
if (m[s[i]] < m[s[i + 1]])
result -= m[s[i]];
else
result += m[s[i]];
}
result += m[s[s.size() – 1]];
return result;
}
private:
unordered_map <char, int> m;
};
Tips:
Beats 85% , however
If I initialize m before considering boundary. It will be much slower (only beats 15%)
class Solution {
public:
int romanToInt(string s) {
m[‘I’] = 1;
m[‘V’] = 5;
m[‘X’] = 10;
m[‘L’] = 50;
m[‘C’] = 100;
m[‘D’] = 500;
m[‘M’] = 1000;
if (s.size() == 0) return 0;
int result = 0;
for (int i = 0; i < s.size() – 1; i++)
{
if (m[s[i]] < m[s[i + 1]])
result -= m[s[i]];
else
result += m[s[i]];
}
result += m[s[s.size() – 1]];
return result;
}
private:
unordered_map <char, int> m;
};