LeetCode #13 - Roman To Integer

November 08, 2020

Howdy happy people 👋! In the last problem we solved, we had to convert the given Integer into its Roman equivalent. In this problem, we are going to do just opposite i.e, we will convert given Roman string into its Integer equivalent.

Roman To Integer

Problem Statement

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.

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].

Examples

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 and IV = 4.

Analysis

This problem is pretty straight forward. We will be given a string representing Roman numeral, and we need to return its corresponding integer.

The length of string cannot be more than 15 and the value of result will not be more than 3999. Some Roman symbols and their equivalent integer values are already given. Only thing we need to notice is the cases where subtraction is used.

Approach

Maintain a map/dictionary with Roman symbols and their corresponding integer equivalent.
Scan the string from right to left. Get the value corresponding to the current character from the map/dictionary and add it to the result.
The special case is where there is a character at left of current character whose value is less than the value corresponding to the current character. For e.g. X represents 10 but IX represents 9. In this case, we will subtract the value of the character in the left from the result.

Let’s take an example where s = MCMXCIV.

result = 0;

i = 'V'
result = 0 + 5 = 5

i = 'I', it is smaller than the character at right
result = 5 - 1 = 4;

i = 'C'
result = 4 + 100 = 104

i = 'X', it is smaller than the character at right
result = 104 - 10 = 94

i = 'M'
result = 94 + 1000 = 1094

i = 'C', it is less than the character at right
result = 1094 - 100 = 994

i = 'M'
result = 994 + 1000 = 1994

And 1994 is the Roman equivalent of MCMXCIV.

Time Complexity

The maximum length of the string can be 15, therefore, the worst case time complexity can be O(15) or O(1).

Space Complexity

We are using map/dictionary to store the Roman symbols and their corresponding integer values but there are only 7 symbols hence the worst case space complexity can be O{7} which is equivalent to O(1).

Code

Java

public class RomanToInteger {

    public int romanToInt(String s) {
        // Map to store romans numerals
        Map<Character, Integer> romanMap = new HashMap<>();
        // Fill the map
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);
        // Length of the given string
        int n = s.length();
        // Variable to store result
        int num = romanMap.get(s.charAt(n - 1));
        // Loop for each character from right to left
        for (int i = n - 2; i >= 0; i--) {
            // Check if the character at right of current character is
            // bigger or smaller
            if (romanMap.get(s.charAt(i)) >= romanMap.get(s.charAt(i + 1))) {
                num += romanMap.get(s.charAt(i));
            } else {
                num -= romanMap.get(s.charAt(i));
            }
        }
        return num;
    }
}

Python

def romanToInt(s: str) -> int:
    # Dictionary of roman numerals
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    # Length of the given string
    n = len(s)
    # This variable will store result
    num = roman_map[s[n - 1]]
    # Loop for each character from right to left
    for i in range(n - 2, -1, -1):
        # Check if the character at right of current character is bigger or smaller
        if roman_map[s[i]] >= roman_map[s[i + 1]]:
            num += roman_map[s[i]]
        else:
            num -= roman_map[s[i]]
    return num

JavaScript

var romanToInt = function (s) {
    // Map to store romans numerals
    const romanMap = new Map();
    // Fill the map
    romanMap.set('I', 1);
    romanMap.set('V', 5);
    romanMap.set('X', 10);
    romanMap.set('L', 50);
    romanMap.set('C', 100);
    romanMap.set('D', 500);
    romanMap.set('M', 1000);
    // Length of the given string
    const n = s.length;
    // Variable to store result
    let num = romanMap.get(s[n - 1]);
    // Loop for each character from right to left
    for (let i = n - 2; i >= 0; i--) {
        // Check if the character at right of current character is
        // bigger or smaller
        if (romanMap.get(s[i]) >= romanMap.get(s[i + 1])) {
            num += romanMap.get(s[i]);
        } else {
            num -= romanMap.get(s[i]);
        }
    }
    return num;
};

Kotlin

fun romanToInt(s: String): Int {
    // Map to store romans numerals
    val romanMap: MutableMap<Char, Int> = HashMap()
    // Fill the map
    romanMap['I'] = 1
    romanMap['V'] = 5
    romanMap['X'] = 10
    romanMap['L'] = 50
    romanMap['C'] = 100
    romanMap['D'] = 500
    romanMap['M'] = 1000
    // Length of the given string
    val n = s.length
    // Variable to store result
    var num = romanMap[s[n - 1]]!!
    // Loop for each character from right to left
    for (i in n - 2 downTo 0) {
        // Check if the character at right of current character is
        // bigger or smaller
        if (romanMap[s[i]]!! >= romanMap[s[i + 1]]!!) {
            num += romanMap[s[i]]!!
        } else {
            num -= romanMap[s[i]]!!
        }
    }
    return num
}

Complete Code

Conclusion

Congratulations 👏! We have solved another problem from LeetCode.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!

Created and maintained by@Anirudh Sharma

I love to learn and share. Hence, this site has no ads, no affiliation links, or any BS. If you like what you see, give me a thumbs up.