Leetcode 13: Roman to Integer

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Approach

Initially, I could not figure out where to start or how to go about this task. So I went through the question again and noticed that the solution was already inside the question. It explained that with Roman numerals, you usually add two or more constant numerals to get some values or subtract two or more numerals to get others. When I say constant numerals, I mean the symbols like I, V, X, L, C, D, M and so on.

With this, the approach becomes clearer. Given a string, the first thing to note is that we have to loop through each character in the string. We then compare each character to the Roman numeral symbols above to get the number value that matches that character.

We also create a variable named total outside the loop with a default value of 0. This variable will be updated every time the loop runs. It stores our running sum.

Inside the loop, compare the current item with the next item.

• If the current item is greater than the next item, add it to total.
• If the current item is less than the next item, subtract it from total.

Whatever result you get becomes the new value of total.

Given a string s = "MCMXCIV":

• Start with total = 0.

Loop through the string:

• Current item M = 1000, next item C = 100. 1000 > 100 → add 1000. total = 1000.
• Current item C = 100, next item M = 1000. 100 < 1000 → subtract 100. total = 900.
• Current item M = 1000, next item X = 10. 1000 > 10 → add 1000. total = 1900.
• Current item X = 10, next item C = 100. 10 < 100 → subtract 10. total = 1890.
• Current item C = 100, next item I = 1. 100 > 1 → add 100. total = 1990.
• Current item I = 1, next item V = 5. 1 < 5 → subtract 1. total = 1989.
• Last item V = 5 (no next item). Just add 5. total = 1994.

So the value of "MCMXCIV" is 1994.

Solution

const romanToInt = (s) => {
  const romanNumerals = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };

  let total = 0;
  for (let i = 0; i < s.length; i++) {
    let curr = s[i];
    let next = s[i + 1];

    if (romanNumerals[curr] < romanNumerals[next]) {


      total-= romanNumerals[curr];
    } else {
      total+= romanNumerals[curr];
    }
  }

  return total;
};

This solution has a time complexity of O(n) linear time. Feel free to drop links to more solutions in the comment below. Let me know what you think.

Comments

[Alex Mustiere]

Here is another solution :

const convertRomanToArabic = (roman: string): number => {
  let counter = 0;

  const manageToken = (token: string, tokenIncrement: number) => {
    while (roman.startsWith(token)) {
      counter += tokenIncrement;
      roman = roman.slice(token.length);
    }
  };

  manageToken('M', 1000);
  manageToken('CM', 900);
  manageToken('D', 500);
  manageToken('CD', 400);
  manageToken('C', 100);
  manageToken('XC', 90);
  manageToken('L', 50);
  manageToken('XL', 40);
  manageToken('X', 10);
  manageToken('IX', 9);
  manageToken('V', 5);
  manageToken('IV', 4);
  manageToken('I', 1);

  return counter;
};