You get a string s that holds a Roman numeral. Return the number it stands for.
Roman numerals use seven letters. Each letter has a value:
I = 1 X = 10 C = 100 M = 1000 V = 5 L = 50 D = 500
Usually the letters go from larger values to smaller ones. Then the number is the sum of their values.
Six pairs break that order. In each one, a smaller letter comes just before a larger one. That smaller letter is subtracted:
IV = 4 IX = 9 XL = 40 XC = 90 CD = 400 CM = 900
Example 1:
Input: s = "XXXI" Output: 31 Explanation: No letter comes before a larger one. So you add them all: 10 + 10 + 10 + 1 = 31.
Example 2:
Input: s = "XIV" Output: 14 Explanation: X is 10. Then comes the pair IV, which is 4. In total, 10 + 4 = 14.
Example 3:
Input: s = "DCCCXLIX" Output: 849 Explanation: D is 500, and CCC is 300. XL is 40, and IX is 9. In total, 500 + 300 + 40 + 9 = 849.
Constraints:
shas 1 to 15 letters.- Each letter is one of the seven above.
- The numeral in
sis always valid. - Its value is from 1 to 3,999.
Your solution should run in O(n) time, where n is the length of s.
Look at each letter together with the letter after it. When the next letter has a larger value, this letter is the first half of a pair like IV.
Subtract a letter's value when the next letter is larger. Otherwise, and for the last letter, add it. In XIV that gives 10 - 1 + 5 = 14.
Each letter takes one lookup in a map of 7 letters and one addition or subtraction: O(n) time.
The map always has 7 entries, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
