Friday, July 15, 2016

Roman To Integer

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

Solution:
class Solution {
public:
    int romanToInt(string s) {
        int num = 0;
        int size = s.size();
        if (size == 0)
            return num;
        // Initialize.
        map<char, int> map;
        map['I'] = 1;
        map['V'] = 5;
        map['X'] = 10;
        map['L'] = 50;
        map['C'] = 100;
        map['D'] = 500;
        map['M'] = 1000;

        num = map[s[size - 1]];
        for (int i = size - 2; i >= 0; i--) {
            if (map[s[i + 1]] > map[s[i]])
                num -= map[s[i]];
            else
                num += map[s[i]];
        }
        return num;
    }
};

=============
class Solution {
public:
    int romanToInt(string s) {
        map<char, int> mp = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
        int ans = 0;
        
        if (s.size() == 0) {
            return ans;
        } else if (s.size() == 1) {
            return mp[s[0]];
        }
        
        int back = -1, cur = 0;
        while (cur < s.size()) {
            ans += mp[s[cur]];
            if (back != -1 && mp[s[back]] < mp[s[cur]]) {
                ans -= (2 * mp[s[back]]);
            }
            back = cur;
            cur++;
        }
        return ans;
    }
};

No comments:

Post a Comment