Understanding LeetCode: 13. Roman To Integer

source: wikihow (How to Use Roman Numerals)

I have been wanting to try LeetCode for a while now and this week I finally decided to give it a go. I created my account and started with the suggested “Challenges For New Users”. And if you landed in this post chances are you’re doing the same.

We all know that one could simply go to the next tab and check the solution, so why would I be solving it again here? The answer is 1: to provide a more in-depth and/or slow-paced explanation; and 2: to hopefully learn and memorize it better myself.

The problem number 13 invites you to build a function capable of, given a string input representing a roman numeral, return it’s equivalent in integers. Within the problem description there is an explanation on how to interpret roman numerals and because of that we’re assuming that there’s no need to explain it again here.

Three scenarios are presented to the user (these will be the standard test cases for your function, but you can add more if you wish):

1. Input: s = ‘III’;
   Expected Output: 3;
2. Input: s = ‘LVIII’;
   Expected Output: 58;
3. Input: s = ‘MCMXCIV’;
   Expected Output: 1994;

Also, three constraints are listed for the problem to be solved:

1. 1 ≤ s.length ≤ 15, or s, the input, is between 1 and 15;
2. s contains only the characters “I”, “V”, “X”, “L”, “C”, “D”, “M”;
3. It is guaranteed that s is a valid roman numeral in the range [1, 3999];

Although the solution to the 13th challenge seemed pretty straightforward to me, in a number of other problems, I was not able to come up with a solution equivalent to the most accepted one, neither as performing, immediately or at the first attempt — as you’ll notice while reading the next posts. So I’m curious: what was the first solution that popped up to your head once your read the description for Roman to Integer?

The text editor provided within LeetCode loads the following structure for the function to be built around:

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function(s) {}

The approach I used for this case — keep in mind I’ll probably be doing this whole series using JavaScript sometimes superset with Typescript — was to have an object containing the values for each of the seven possible input characters:

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function(s: string) {
    const chars: Record<string, number> = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    };
};

Next, we know that JavaScript allows us to access strings using indexes, as if they were arrays, so we are going to initialize a result variable and iterate through the string input left to right by starting the “i” index at 0 and stopping once it reaches the strings length, and adding one for each iteration.

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function(s: string) {
  const chars: Record<string, number> = {
      '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++) {}
};

Inside the for loop, we need to declare two more variables: “cur”, to store the current value, and “next”, to store the next value to be read. For that, we’re accessing the “s” string with the loop index “i” and using the “chars” object to know which number that character represents.

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function(s: string) {
  const chars: Record<string, number> = {
      '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++) {
    let cur = chars[s[i]];
    let next = chars[s[i + 1]];
  }
};

The next step to the solution can be considered the core rule for it to work properly and with any given input. The main instruction when reading roman numerals is (or should be imo) that when the current character represents a number smaller than the next one, the current should be subtracted from the next and be read as one. Also, no character repeats itself more than three times, meaning, for example, that if you would represent the number four, you would write “IV” (subtract one from five) in romans, instead of “IIII”.

As we already know in “chars” the value of every single character that can be inputted, and also know the values for current “cur” and next “next”, all we have to do to implement the logic described in the previous paragraph is to check whether “cur” is less than “next”. If false, simply add “cur” to “result”. If true, subtract “cur” from “next” and sum the resulted value to “result”. Don’t forget to increment your index in the latter situation.

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function(s: string) {
  const chars: Record<string, number> = {
      '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++) {
    let cur = chars[s[i]];
    let next = chars[s[i + 1]];

    if (cur > next) {
      result += cur;
    } else {
      result += next - cur;
      i++;
    }
  }
};

Finally, after the loop is finished, we can return the result containing the sum of all the values read from right left to right:

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function(s: string) {
  const chars: Record<string, number> = {
      '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++) {
    let cur = chars[s[i]];
    let next = chars[s[i + 1]];

    if (cur > next) {
      result += cur;
    } else {
      result += next - cur;
      i++;
    }
  }

  return result;
};

It should be reinforced that this is not supposed to be the definitive or standard solution to LeetCode’s problem 13, although it seems to be among the most popular ones for JS the last time I checked.

Did you find any mistakes in the text above? Chances are you did, as I wrote and edited it myself as a non-native English speaker, so feel free to reach out to point them so I can improve it for the next readers. It’ll be greatly appreciated.

Talk soon,