Problem
Given a Roman numeral, convert it to an integer. Roman numerals: I=1, V=5, X=10, L=50, C=100, D=500, M=1000.
Example
Input: "IX"
Output: 9Input: "MCMXCIV"
Output: 1994Solution
Walk left to right. If current value is less than next, subtract it. Otherwise add it.
def roman_to_int(s):
values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
total = 0
for i in range(len(s)):
if i + 1 < len(s) and values[s[i]] < values[s[i+1]]:
total -= values[s[i]]
else:
total += values[s[i]]
return totalfunction romanToInt(s) {
const values = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
let total = 0;
for (let i = 0; i < s.length; i++) {
if (i + 1 < s.length && values[s[i]] < values[s[i+1]]) total -= values[s[i]];
else total += values[s[i]];
}
return total;
}int romanToInt(string s) {
unordered_map<char, int> v = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); i++) {
if (i + 1 < s.size() && v[s[i]] < v[s[i+1]]) total -= v[s[i]];
else total += v[s[i]];
}
return total;
}public int romanToInt(String s) {
Map<Character, Integer> v = new HashMap<>();
v.put('I',1); v.put('V',5); v.put('X',10); v.put('L',50);
v.put('C',100); v.put('D',500); v.put('M',1000);
int total = 0;
for (int i = 0; i < s.length(); i++) {
if (i + 1 < s.length() && v.get(s.charAt(i)) < v.get(s.charAt(i+1))) {
total -= v.get(s.charAt(i));
} else {
total += v.get(s.charAt(i));
}
}
return total;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Roman numerals use subtractive notation (IV = 4, IX = 9). When a smaller value precedes a larger one, it gets subtracted. Otherwise it adds.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?