13. Roman to Integer - Solved in Ruby/Python/Java/C++/JavaScript/C#/Go

LeetCode Python/Java/C++/JS > 13. Roman to Integer > Solved in Ruby, Python, Java, C++, JavaScript, C#, Go > GitHub

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 <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Topics

Stack

Hint 1

Problem is simpler to solve by working the string from back to front and using a map.

Intuition
Previous Next

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 of result?
Click to view the answer
Subtract "the value of the previous character * 2".

👋 Hi, I'm the developer behind coder.id — Build your programmer brand. Create your portfolio, resume, and blog in minutes, and land your dream offer!

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 #

# Solution 1.
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


# Solution 2
class Solution:
    def romanToInt(self, s: str) -> int:
        ans = 0
        r_to_v = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        prev = None

        for i in range(len(s) - 1, -1, -1): # iterate from right to left
            value = r_to_v[s[i]]
            if prev and prev // value in (5, 10):
                ans -= value
            else:
                ans += value
            prev = value

        return ans

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 GitHub repo -> 13. Roman to Integer. Thanks!

Previous Next

Level Up Your Developer Identity

📄 Resume, Portfolio & Blog

🌐 Custom Domain Binding Supported

✨ Premium Subdomain: https://yourname.coder.id

Build Your Developer Brand at coder.id →

Unregistered user

All solutions

Welcome !