Roman to Integer - Leet Code Problem

Problem Statement

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

Symbols

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.

Examples:

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.

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

Approach 1

#include <iostream>
#include <map>
#include <string>

using namespace std;
class Solution{
    map<char, int> values = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};

public:
    int romanToInt(string s){
        int total = values.at(s.at(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--){
            int after = values.at(s.at(i + 1));
            int current = values.at(s.at(i));
            if (after > current){
                total -= current;
            }
            else{
                total += current;
            }
        }
        return total;
    }
};

int main(){
    int value = Solution().romanToInt("CXL");
    cout << value;
}

This is the simple and best approach for solving this problem:-

We have taken an integer variable total and stored the value of the Last Roman letter from string s.
Created a loop that runs in decreasing order from the length of s-2 to 0.
- If the value of the Roman letter at i+1 > i then, we have to subtract the value at i from the total otherwise, we have to add.
return the total

Let's take an example:

if s="CXL" which is 140.

When the code runs, total = 50 :

after = 50 (L) and current = 10 (X); after>current = true;
total=50-10 = 40 ;
after = 10 (X) and current = 100 (C); after>current=false;
total=40+100=140;

Approach 2

#include <iostream>
#include <map>
#include <string>

using namespace std;
class Solution{
    map<char, int> values = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
    map<string, int> replaceValues = {{"IV", 4},
                                      {"IX", 9},
                                      {"XL", 40},
                                      {"XC", 90},
                                      {"CD", 400,
                                      {"CM",900;

public:
    int romanToInt(string s){
        int i = 0, total = 0;
        while (i < s.length()){
            string ss = s.substr(i, 2);
            if (replaceValues.find(ss) != replaceValues.end()){
                total += replaceValues.at(ss);
                i++;
            }else{
                total += values.at(s.at(i));
            }
            i++;
        }
        return total;
    }
};

int main(){
    int value = Solution().romanToInt("CXL");
    cout << value << endl;
}

In this approach,

We started the loop from 0 to length of s
- ss is substring, which always finds two characters as a string in the replaceValues map if the values exist, then the total will be incremented by the value of that Roman number at replaceValues map and also increment i by 1.
- Otherwise, the total will be incremented by the value of the Roman number at i index of values map.
- At the end increment i by 1.

Example: