Roman Numeral to Integer Editorial

Practice Problem Link: Roman Number To Integer | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a roman numeral s, convert it to an integer.

Approach

The roman numbers are written in descending order according to the value of the character except for the case of subtraction. The algorithm to solve the problem is based on the same fact.

• First, create a function that returns the integer value for the corresponding character.
• Initialize the answer with the value at 0^th index.
• Traverse the string and check two consecutive indices. If the value at i^th index is greater than the value at (i -1)^th index then subtract the value at (i - 1)^th index from the answer twice(as it was added in the previous step) and add the value at i^th index. Otherwise, just add the value at i^th index in the answer.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int romanValue (char romanLetter) {
   if (romanLetter == 'I') {
       return 1;
   }
   if (romanLetter == 'V') {
       return 5;
   }
   if (romanLetter == 'X') {
       return 10;
   }
   if (romanLetter == 'L') {
       return 50;
   }
   if (romanLetter == 'C') {
       return 100;
   }
   if (romanLetter == 'D') {
       return 500;
   }
   if (romanLetter == 'M') {
       return 1000;
   }
}
int romanToInt(string s) {
   int ans = romanValue(s[0]);
   for (int i = 1; i < s.size(); i++) {
       if (romanValue(s[i]) > romanValue(s[i - 1])) {
           ans = ans - (2 * romanValue(s[i - 1])) + romanValue(s[i]);
       } else {
           ans += romanValue(s[i]);
       }
   }
   return ans;
}

Java

class Solution {
   int romanValue (char romanLetter) {
       if (romanLetter == 'I') {
           return 1;
       }
       if (romanLetter == 'V') {
           return 5;
       }
       if (romanLetter == 'X') {
           return 10;
       }
       if (romanLetter == 'L') {
           return 50;
       }
       if (romanLetter == 'C') {
           return 100;
       }
       if (romanLetter == 'D') {
           return 500;
       }
       if (romanLetter == 'M') {
           return 1000;
       }
       return 0;
   }
   int romanToInt(String s) {
       int ans = romanValue(s.charAt(0));
       for (int i = 1; i < s.length(); i++) {
           if (romanValue(s.charAt(i)) > romanValue(s.charAt(i - 1))) {
               ans = ans - (2 * romanValue(s.charAt(i - 1))) + romanValue(s.charAt(i));
           } else {
               ans += romanValue(s.charAt(i));
           }
       }
       return ans;
   }
}