Roman to Integer

we are given a Roman number and we have a dictionary that enlists integer values corresponding to each Roman number. the dictionary is as follows

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 27 can be written as XXVII, which is XX + V + II i.e. 10 + 10 + 5 + 1 + 1 = 27.

To create the number 9, we write it as IX i.e. IntegerValue(X) - IntegerValue(I) = 10 - 1 = 9.

So, this is the case, when we have a Roman number lesser than the next number, then we simply subtract the value of this current number from the value of the next number.

Solution:

The solution to the problem is simple

1. we simply prepare a hashmap for <roman, integer> pair.

2. Initialize an answer to 0, and iterate over the given string s, and for each character, if the corresponding value for that is lesser than the value of the next Roman number then subtract the values of this current Roman character from the answer.

3. Otherwise, add the value of the current Roman character.

4. Finally, return the answer.

int romanToInt(string s) {
          int ans = 0;

          unordered_map<int,int>mp;
          mp['I'] = 1;
          mp['V'] = 5;
          mp['X'] = 10;
          mp['L'] = 50;
          mp['C'] = 100;
          mp['D'] = 500;
          mp['M'] = 1000;

          int n = s.length();

          for(int i=0;i<n;i++){
                if(mp[s[i]] < mp[s[i+1]]){
                     ans -= mp[s[i]];
                }else{
                     ans += mp[s[i]];
                }
          }

          return ans;
    }

Let's discuss the time and space complexity.

The time complexity for this solution is O(N) where N is the length of the string s.

The space complexity is O(N) because we are using the unordered map.