Roman to Integer

Sep 24, 2023#leetcode#dsa

The Roman to Integer problem on LeetCode is a common coding challenge that asks you to convert a Roman numeral represented as a string into an integer.

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 a numeral system that originated in ancient Rome and were used throughout the Roman Empire. They are still used today in some contexts, such as numbering the chapters or sections of books, indicating the copyright dates of books, and for decorative purposes. Roman numerals use a combination of letters from the Latin alphabet to represent numbers.

Roman Integer
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

Here’s how Roman numerals work:

  • Roman numerals are written from left to right.
  • When a smaller number appears before a larger number, you subtract the smaller number. For example, IV represents 4=514 = 5 - 1, and IX represents 9=1019 = 10 - 1.
  • When a smaller number appears after a larger number, you add the smaller number. For example, VII represents 7=5+27 = 5 + 2, and XIV represents 14=10+1+314 = 10 + 1 + 3.
  • You can repeat a symbol up to three times in a row to add its value. For example, III represents 3=1+1+13 = 1 + 1 + 1.
  • You can’t repeat the same subtractive pair more than once. For example, 44 is represented as IV, not IIII, and 99 is represented as IX, not VIIII.

To convert a Roman numeral string into an integer, you need to add up the values of the individual symbols while considering a special rule: If a smaller symbol appears before a larger symbol, you should subtract the value of the smaller symbol.

Here’s solution in C++:

#include <cassert>
#include <iostream>
#include <unordered_map>

using namespace std;

int romanToInt(string s) {
  unordered_map<char, int> romanNumerals = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000}
  };

  int result = 0;
  int prevValue = 0;

  for (int i = s.length() - 1; i >= 0; i--) {
    int currentValue = romanNumerals[s[i]];

    if (currentValue < prevValue) {
      result -= currentValue;
    } else {
      result += currentValue;
    }

    prevValue = currentValue;
  }

  return result;
}

int main() {
  // Test cases with assertions
  assert(romanToInt("III") == 3);
  assert(romanToInt("IV") == 4);
  assert(romanToInt("IX") == 9);
  assert(romanToInt("LVIII") == 58);
  assert(romanToInt("MCMXCIV") == 1994);

  cout << "All test cases passed!" << endl;

  return 0;
}

The solution uses a mapping of Roman numeral characters to their integer values and iterates through the input string, adjusting the result based on the current and next characters as per the rules. It covers the basic symbols and the subtractive combinations as required to handle valid Roman numerals.