A simple solution using stack. Any better solution?


  • 0
    M

    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;
        }
    };

  • 0
    S

    My solution, only scan string once.
    (about roman number)

    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;
    }
    

  • 1
    O

    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;
    }
    

    };


  • 0
    S

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


  • 0
    X

    This is clever. Thanks for sharing!


Log in to reply
 

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