13. Roman to Integer

Description

Given a roman numeral, convert it to an integer.

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

Solution

Iterative, time O(n), space O(1)

找规律，升序的"ab"中需要减a加b，降序或相等则直接加a即可。貌似roman表达中升序序列长度都是2。

class Solution {
    public int romanToInt(String s) {
        String t = "IVXLCDM";
        int[] nums = {1, 5, 10, 50, 100, 500, 1000};
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); ++i) {
            map.put(t.charAt(i), nums[i]);
        }
        
        s += "I";   // trick
        int val = 0;
        for (int i = 0; i < s.length() - 1; ++i) {
            if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                val -= map.get(s.charAt(i));
            } else {
                val += map.get(s.charAt(i));
            }
        }
        
        return val;
    }
}