A 36ms C++ Solution, No Hashmap, Clean to understand


  • 10
    A

    The key is to check if the i-th char is smaller than (i+1)th, If so, then it should be a negative.
    Add them all is the result.

    class Solution {
    public:
        int romanToInt(string s) {
    	    int num[256] = { 0 };
    	    int result = 0;
    	    num['I'] = 1; num['V'] = 5; num['X'] = 10; num['L']=50;
    	    num['C'] = 100; num['D'] = 500; num['M'] = 1000;
    	    int i = 0;
    	    while (i < s.size()){
    		    if (num[s[i]] < num[s[i+1]])
    			    result -= num[s[i]];
    		    else
    			    result += num[s[i]];
    		    i++;
    	    }
    	    return result;
        }
    };

  • 0
    class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        Num = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}
        L = len(s)
        sum = 0
        i = 0
        
        while(i < L - 1):
    
            if(Num.get(s[i]) < Num.get(s[i + 1])):
                sum -= Num.get(s[i])
            else:
                sum += Num.get(s[i])
            i += 1
        sum += Num.get(s[i])
        return sum

  • 0

    Yes,your alogrithm is easy to understand


  • 0
    A

    for the last i in while loop that i = s.size() - 1;

    won't the following overflow?

    if (num[s[i]] < num[s[i+1]])

  • 1
    A

    i+1 may be equal to s.size(), but it will not bring problem because num[i+1] is 0. There will not be out-of-range problem. So no overflow. If the size of num is only 7, then overflow may come out.


  • 0
    N

    @Andrinux,

    I think @aileenbai suggested s[i+1] already run out of index, and then num[s[i+1]] is an undefined behaviour.


  • 0

    @needforspeed s[i+1] will have no problem. But when you use s.at(i+1), this can cause an undefined behaviour.


  • 0
    This post is deleted!

  • 0
    K

    @Andrinux
    Can you please tell me why mine is not working for MCMXCVI ?

    class Solution {
    public int romanToInt(String s) {
    Map <Character,Integer> map=new HashMap<Character,Integer>();
    map.put('I', 1);
    map.put('V', 5);
    map.put('X', 10);
    map.put('L', 50);
    map.put('C', 100);
    map.put('D', 500);
    map.put('M', 1000);
    Character c;
    int l = s.length();
    int val,pval=1000;
    int n=0;
    for(int i=0;i<l;i++)
    {
    c=s.charAt(i);
    val=map.get(c);
    if(val<=pval)
    n+=val;
    else
    n-=val;
    pval=val;

        }
        return n;
    }
    

    }


Log in to reply
 

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