Roman to Integer
Easy · Math · Hash Table · Math · String
Problem
Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Symbols are normally written from largest to smallest, and their values are added.
Six subtractive pairs break that rule: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900. In each, a smaller symbol written before a larger one is subtracted from it.
Given a valid Roman numeral s, return the integer it represents.
Examples
Input: s = "XXVII" Output: 27
X + X + V + I + I = 27. Every symbol is at least as large as the one after it.
Input: s = "CDXLIV" Output: 444
CD = 400, XL = 40 and IV = 4.
Input: s = "MMXIX" Output: 2019
MM = 2000, X = 10 and IX = 9.
Constraints
- 1 <= len(s) <= 15
- s contains only the characters I, V, X, L, C, D, M
- s is a valid Roman numeral in the range [1, 3999]
Approaches
- Baseline: write every numeral until one matches — time O(N · L), N = 3999 numerals of length L <= 15, space O(L)
Follow-up
Going the other way, from an integer to a numeral, is a greedy walk over the thirteen values 1000, 900, 500, 400, … 1. Why does taking the largest value that fits always give the standard numeral?
Related problems
Start free on Cariara · Coding problems · System design studio
