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!

Log in to reply
 

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