LeetCode: Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

---

This problem is similar to the previous one. Just keep in mind that we need to consider the letter next to the current one.

C++ Code non-recursive:

/*
 * func: roman_to_int
 * goal: convert roman numerial to integer
 * @param s: input roman numeral string
 * return: return the int integer
 */
/*
 * check every possibility
 */
int roman_to_int(string &s){
    assert(s.length() > 0);
    
    int ret = 0;
    int idx = 0;
    //Append an unused char to the tail in case of idx+1
    s += 'A';
    int length = static_cast<int>(s.length());
    while(idx < length){
        if(s[idx] == 'M'){
            ret += 1000;
            ++idx;
        }else if(s[idx] == 'C' && s[idx+1] == 'M'){
            ret += 900;
            idx += 2;
        }else if(s[idx] == 'C' && s[idx+1] == 'D'){
            ret += 400;
            idx += 2;
        }else if(s[idx] == 'C'){
            ret += 100;
            ++idx;
        }else if(s[idx] == 'D'){
            ret += 500;
            ++idx;
        }else if(s[idx] == 'X' && s[idx+1] == 'C'){
            ret += 90;
            idx += 2;
        }else if(s[idx] == 'X' && s[idx+1] == 'L'){
            ret += 40;
            idx += 2;
        }else if(s[idx] == 'X'){
            ret += 10;
            ++idx;
        }else if(s[idx] == 'L'){
            ret += 50;
            ++idx;
        }else if(s[idx] == 'I' && s[idx+1] == 'X'){
            ret += 9;
            idx += 2;
        }else if(s[idx] == 'I' && s[idx+1] == 'V'){
            ret += 4;
            idx += 2;
        }else if(s[idx] == 'V'){
            ret += 5;
            ++idx;
        }else if(s[idx] == 'I'){
            ret += 1;
            ++idx;
        }else{
            ++idx;
        }
    }
    return ret;
}

C++ Code recursive:

int _romanToInt(string s, int index, int result){
    if(index == s.size())
        return result;
    if(s[index] ==  'M')
        return result + 1000 + _romanToInt(s, index+1, result);
    if(s[index] == 'D')
        return result + 500 + _romanToInt(s, index+1, result);
    if(s[index] == 'C'){
        if(((index + 1) != s.size()) && s[index+1] == 'D')
            return result + 400 + _romanToInt(s, index+2, result);
        else if(((index + 1) != s.size()) && s[index+1] == 'M')
            return result + 900 + _romanToInt(s, index+2, result);
        else
            return result + 100 + _romanToInt(s, index+1, result);
    }
    if(s[index] == 'L')
        return result + 50 + _romanToInt(s, index+1, result);
    if(s[index] == 'X'){
        if(((index + 1) != s.size()) && s[index+1] == 'L')
            return result + 40 + _romanToInt(s, index+2, result);
        else if(((index + 1) != s.size()) && s[index+1] == 'C')
            return result + 90 + _romanToInt(s, index+2, result);
        else
            return result + 10 + _romanToInt(s, index+1, result);
    }
    if(s[index] == 'V')
        return result + 5 + _romanToInt(s, index+1, result);
    if(s[index] == 'I'){
        if(((index + 1) != s.size()) && s[index+1] == 'V')
            return result + 4 + _romanToInt(s, index+2, result);
        else if(((index + 1) != s.size()) && s[index+1] == 'X')
            return result + 9 + _romanToInt(s, index+2, result);
        else
            return result + 1 + _romanToInt(s, index+1, result);
    }
    return result;
}

int romanToInt(string s){
    int index = 0;
    int result = 0;
    return _romanToInt(s, index, result);
}

For the python code, we try to solve it in another way. We can calculate from the end to the start. Thus, for cases like 'IV', we can add 5 first and then subtract 1.

Python Code:

# func: convert a roman numeral to a integer
# @param s: input roman numeral string
# @return: return integer
def roman_to_integer(s):
    assert s
    #The dictionary to store the roman-int conversion
    roman_dict = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500,
                  'M': 1000}

    ret = roman_dict[s[-1]]

    for i in range(2, len(s)+1):
        if roman_dict[s[1-i]] <= roman_dict[s[-i]]:
            ret += roman_dict[s[-i]]
        else:
            ret -= roman_dict[s[-i]]

    return ret

I looked at this method online and thought it is very concise. It tries to solve the problem in a reversed order way to avoid consider every two-letter combination separately. However, I compared the running time of this code with mine in C++. This code is a little bit slower (388ms vs 284ms). I think the reason is that it includes comparison in each iteration and more arithmetic calculations since it add one number first and then subtract one. But it is a really good idea.

Reference Link:

1.Roman numerals: http://en.wikipedia.org/wiki/Roman_numerals

2.Roman to Integer - LeetCode: http://discuss.leetcode.com/questions/195/roman-to-integer