# A simple solution using stack. Any better solution?

• Solution using stack and maps. Complexity: O(n)

``````class Solution {
public:

int romanToInt(string s) {
map<char, int> m;
m['I']=1;
m['V']=5;
m['X']=10;
m['L']=50;
m['C']=100;
m['D']=500;
m['M']=1000;

int ans=0;
char temp;

stack<char> st;
st.push(s[0]);

for(int i=1; i<s.size(); i++)
{
if(m[s[i]] >  m[st.top()] )   //special case check
{
temp=st.top();
st.pop();
ans=ans- m[temp];   //if special, subtract the value
st.push(s[i]);
}
else
st.push(s[i]);
}

while(!st.empty())     //calculate the final answer from stack elements
{
ans+= m[ st.top() ];
st.pop();
}

return ans;
}
};``````

• My solution, only scan string once.

``````int romanToInt(string s)
{
int out = 0;
map<char, int> stand = {
{ 'I', 1 },
{ 'V', 5 },
{ 'X', 10 },
{ 'L', 50 },
{ 'C', 100 },
{ 'D', 500 },
{ 'M', 1000 } };

for (int i = 0; i < s.size(); i++) {
if ((i + 1) < s.size() && stand[s[i]] < stand[s[i + 1]]) {
out += stand[s[i + 1]] - stand[s[i]];
i++;
}
else
out += stand[s[i]];
}

return out;
}
``````

• I did a reverse reading of the roman number:

class Solution {

``````map<char, int> val = {
{ 'I', 1 },
{ 'i', 1 },
{ 'V', 5 },
{ 'v', 5 },
{ 'X', 10 },
{ 'x', 10 },
{ 'L', 50 },
{ 'l', 50 },
{ 'C', 100 },
{ 'c', 100 },
{ 'D', 500 },
{ 'd', 500 },
{ 'M', 1000 },
{ 'm', 1000 } };
``````

public:

``````int romanToInt(string s) {
int num = 0;
int last_val = 0;
unsigned int elems = s.length();
for (int i = elems -1; i >= 0; i--)
{
int curr_val = val[s[i]];
if (curr_val >= last_val) {
num += curr_val;
last_val = curr_val;
}
else {
num -= curr_val;
}
}
return num;
}
``````

};

• Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.

• This is clever. Thanks for sharing!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.