Roman to Integer
Parse a Roman numeral into its integer value — subtract when a smaller numeral precedes a larger.
3 min read
hash-map strings
Problem#
Convert a Roman numeral string (I, V, X, L, C, D, M) to its integer value.
Examples#
"III"→3."LVIII"→58."MCMXCIV"→1994.
Constraints#
1 <= s.length <= 15,sis a valid Roman numeral in[1, 3999].
Hints#
Hint
Each character contributes its value, but subtract instead of add when followed by a strictly larger character.
Approach#
Map each Roman symbol to its value. Walk left to right; if value[s[i]] < value[s[i+1]], subtract; else add.
Solution#
class Solution {public: int romanToInt(string s) { unordered_map<char,int> v = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int n = s.size(), ans = 0; for (int i = 0; i < n; ++i) { if (i + 1 < n && v[s[i]] < v[s[i+1]]) ans -= v[s[i]]; else ans += v[s[i]]; } return ans; }};func romanToInt(s string) int { v := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} n, ans := len(s), 0 for i := 0; i < n; i++ { if i+1 < n && v[s[i]] < v[s[i+1]] { ans -= v[s[i]] } else { ans += v[s[i]] } } return ans}class Solution: def romanToInt(self, s: str) -> int: v = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} n, ans = len(s), 0 for i in range(n): if i + 1 < n and v[s[i]] < v[s[i + 1]]: ans -= v[s[i]] else: ans += v[s[i]] return ansfunction romanToInt(s) { const v = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 }; const n = s.length; let ans = 0; for (let i = 0; i < n; i++) { if (i + 1 < n && v[s[i]] < v[s[i + 1]]) ans -= v[s[i]]; else ans += v[s[i]]; } return ans;}class Solution { 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 n = s.length(), ans = 0; for (int i = 0; i < n; i++) { if (i + 1 < n && v.get(s.charAt(i)) < v.get(s.charAt(i + 1))) ans -= v.get(s.charAt(i)); else ans += v.get(s.charAt(i)); } return ans; }}function romanToInt(s: string): number { const v: Record<string, number> = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 }; const n = s.length; let ans = 0; for (let i = 0; i < n; i++) { if (i + 1 < n && v[s[i]] < v[s[i + 1]]) ans -= v[s[i]]; else ans += v[s[i]]; } return ans;}Editorial#
Subtractive notation (IV = 4, CM = 900) is the only twist. The rule “smaller before larger means subtract” is purely local — one lookahead character is all we need. For raw speed, replace the hash map with a 128-entry int[] indexed by character.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#