Given a roman numeral, convert it to an integer.

The answer is guaranteed to be within the range from 1 to 3999.

What is Roman Numeral?

• https://en.wikipedia.org/wiki/Roman_numerals
• https://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97
• http://baike.baidu.com/view/42061.htm

IV -> 4

XII -> 12

XXI -> 21

XCIX -> 99

Observation:  if s.charAt(i) > s.charAt(i - 1), it means we need to subtract the mapped value of s.charAt(i - 1) from the mapped value of s.charAt(i).

Based on this observation, the following algorithm is developed.

1. init result to m.get(s.charAt(length - 1)), the mapped value of the last character.

2. starting from the 2nd last character, iterate through the string from right to left; if the current character‘s mapped value is smaller than

its right neighbor‘s, subtract this mapped value from the result; if not, add this mapped value to the result.

 1 public class Solution {
 2      public int romanToInt(String s) {
 3         if (s == null || s.length()==0) {
 4                 return 0;
 5         }
 6         Map<Character, Integer> m = new HashMap<Character, Integer>();
 7         m.put(‘I‘, 1);
 8         m.put(‘V‘, 5);
 9         m.put(‘X‘, 10);
10         m.put(‘L‘, 50);
11         m.put(‘C‘, 100);
12         m.put(‘D‘, 500);
13         m.put(‘M‘, 1000);
14 
15         int length = s.length();
16         int result = m.get(s.charAt(length - 1));
17         for (int i = length - 2; i >= 0; i--) {
18             if (m.get(s.charAt(i + 1)) <= m.get(s.charAt(i))) {
19                 result += m.get(s.charAt(i));
20             } else {
21                 result -= m.get(s.charAt(i));
22             }
23         }
24         return result;
25     }
26 }

Related Problems

Integer to Roman