LeetCode Python/Java/C++/JS > Stack and Queue > 13. Roman to Integer > Solved in Ruby, Python, Java, C++, JavaScript, C#, Go > GitHub or Repost
LeetCode link: 13. Roman to Integer, difficulty: Easy.
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Example 2:
Input: s = "IV"
Output: 4
Example 3:
Input: s = "IX"
Output: 9
Example 4:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.
Constraints:
1 <= s.length <= 15scontains only the characters('I', 'V', 'X', 'L', 'C', 'D', 'M').- It is guaranteed that
sis a valid roman numeral in the range[1, 3999].
Hint 1
Problem is simpler to solve by working the string from back to front and using a map.
Intuition
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
- The character-to-value mapping can be done using a
Map. - Intuitively, you add the value of each number you encounter to
result, iterating from left to right. - But consider cases like
IV, where the value of the current character is greater than the value of the previous character. In this case, how should you update the value ofresult?Click to view the answer
Subtract "the value of the previous character * 2".
Complexity
Time complexity
O(N)
Space complexity
O(1)
Ruby #
# @param {String} s
# @return {Integer}
def roman_to_int(s)
char_to_num = {
"I" => 1,
"V" => 5,
"X" => 10,
"L" => 50,
"C" => 100,
"D" => 500,
"M" => 1000,
}
result = 0
s.chars.each_with_index do |c, i|
result += char_to_num[c]
next if i == 0
if char_to_num[s[i - 1]] < char_to_num[c]
result -= char_to_num[s[i - 1]] * 2
end
end
result
end
Python #
class Solution:
def romanToInt(self, s: str) -> int:
char_to_num = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
result = 0
for i, c in enumerate(s):
result += char_to_num[c]
if i == 0:
continue
# If the previous value is smaller than the current,
# subtract it twice (once because it was added, once for the rule)
if char_to_num[s[i - 1]] < char_to_num[c]:
result -= char_to_num[s[i - 1]] * 2
return result
Java #
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> charToNum = new HashMap<>();
charToNum.put('I', 1);
charToNum.put('V', 5);
charToNum.put('X', 10);
charToNum.put('L', 50);
charToNum.put('C', 100);
charToNum.put('D', 500);
charToNum.put('M', 1000);
int result = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
result += charToNum.get(c);
if (i == 0) {
continue;
}
// If previous value is smaller than current, subtract it twice
if (charToNum.get(s.charAt(i - 1)) < charToNum.get(c)) {
result -= charToNum.get(s.charAt(i - 1)) * 2;
}
}
return result;
}
}
C++ #
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> char_to_num = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int result = 0;
for (int i = 0; i < s.length(); i++) {
result += char_to_num[s[i]];
if (i == 0) continue;
// If the previous character's value is less than the current,
// subtract that previous value twice.
if (char_to_num[s[i - 1]] < char_to_num[s[i]]) {
result -= char_to_num[s[i - 1]] * 2;
}
}
return result;
}
};
JavaScript #
/**
* @param {string} s
* @return {number}
*/
const romanToInt = function(s) {
const charToNum = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
let result = 0;
for (let i = 0; i < s.length; i++) {
const currentVal = charToNum[s[i]];
result += currentVal;
if (i === 0) {
continue;
}
const prevVal = charToNum[s[i - 1]];
// If the previous value is smaller than the current,
// subtract it twice (adjusting for the previous addition)
if (prevVal < currentVal) {
result -= prevVal * 2;
}
}
return result;
};
C# #
public class Solution
{
public int RomanToInt(string s)
{
var charToNum = new Dictionary<char, int>
{
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int result = 0;
for (int i = 0; i < s.Length; i++)
{
int currentVal = charToNum[s[i]];
result += currentVal;
if (i == 0)
{
continue;
}
int prevVal = charToNum[s[i - 1]];
// If the previous value is less than the current,
// subtract it twice to correct the total.
if (prevVal < currentVal)
{
result -= prevVal * 2;
}
}
return result;
}
}
Go #
func romanToInt(s string) int {
charToNum := map[rune]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
result := 0
// Converting string to a slice of runes for easy indexing
runes := []rune(s)
for i, c := range runes {
result += charToNum[c]
if i == 0 {
continue
}
// If the previous value is smaller than the current,
// subtract it twice (adjusting for the previous addition)
if charToNum[runes[i - 1]] < charToNum[c] {
result -= charToNum[runes[i - 1]] * 2
}
}
return result
}
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 13. Roman to Integer. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
- π Free Custom Domain: Bind your own personal domain for freeβforever.
- β¨ Premium Subdomains: Stand out with elite tech handle like
name.leader.me.