Wednesday, January 7, 2015

LeetCode 13: Roman to Integer

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
public class Solution {
    public int romanToInt(String s) {
        // Compare left element with right element
        // If left < right, result -= left (e.g., IV(4));
        // If left > right, result += left (e.g., XI(11), XLV(45)).
        Map<Character, Integer> map = new HashMap<>();
        
        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);
        
        int n = s.length();
        
        int right = map.get(s.charAt(n-1));
        int left;
        int ret = right;
        
        if (n == 1)
            return ret;
            
        for (int i = n-2; i >= 0; i--)
        {
            left = map.get(s.charAt(i));
            
            if (left < right)
                ret -= left;
            else
                ret += left;
                
            right = left;
        }
        
        return ret;
    }
}

No comments:

Post a Comment