DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode Roman to Integer

Problem statement

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

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

For example, 2 is written as II in Roman numeral, just two one's 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.

Given a roman numeral, convert it to an integer.

Problem statement taken from: https://leetcode.com/problems/roman-to-integer

Example 1:

Input: s = "III"
Output: 3
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: s = "IV"
Output: 4
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: s = "IX"
Output: 9
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Enter fullscreen mode Exit fullscreen mode

Example 5:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Enter fullscreen mode Exit fullscreen mode

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].
Enter fullscreen mode Exit fullscreen mode

Explanation

The solution to this problem is simple.
We need to pay attention to the order of Roman characters
in the string.

We represent 4 by IV instead of IIII.
This gives a hint if we need to subtract the current value of the character
or add it to the total sum.

Algorithm

- initialize an hash map characterMap with keys as 'I', 'V', 'X', 'L', 'C', 'D', 'M'
  and value as 1, 5, 10, 50, 100, 500, 1000.
- return 0 if s.length() == 0.

- if s.length == 1, return characterMap[s[0]]

- set sum = characterMap[s[s.length() - 1]].
  - characterMap[s[s.length() - 1]] is the value of the last character in the string s.

- Loop for i = s.length() - 2; i >= 0; i--
  // if value of the current character is less than next character we subtract current value from sum
  - if characterMap[s[i]] < characterMap[s[i+1]]
    - subtract sum = sum - characterMap[s[i]]
  - else
    - add sum = sum + characterMap[s[i]]

- return sum
Enter fullscreen mode Exit fullscreen mode
C++ solution
class Solution {
public:
    int romanToInt(string s) {
        map<char, int> characterMap = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

        int length = s.length();

        if(length == 0) {
            return 0;
        }

        if(length == 1){
            return characterMap[s[0]];
        }

        int sum = characterMap[s[length - 1]];
        for(int i = length - 2; i >= 0; i--){
            if(characterMap[s[i]] < characterMap[s[i+1]]){
                sum -= characterMap[s[i]];
            } else {
                sum += characterMap[s[i]];
            }
        }

        return sum;
    }
};
Enter fullscreen mode Exit fullscreen mode
Golang solution
func romanToInt(s string) int {
    characterMap := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    length := len(s)

    if length == 0 {
        return 0
    }

    if length == 1 {
        return characterMap[s[0]]
    }

    sum := characterMap[s[length - 1]]

    for i := length - 2; i >= 0; i-- {
        if characterMap[s[i]] < characterMap[s[i+1]] {
            sum -= characterMap[s[i]]
        } else {
            sum += characterMap[s[i]]
        }
    }

    return sum
}
Enter fullscreen mode Exit fullscreen mode
Javascript solution
var romanToInt = function(s) {
    const characterMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    const length = s.length;

    if( length == 0 ) {
        return 0;
    }

    if( length == 1 ){
        return characterMap[s[0]];
    }

    var sum = characterMap[s[length - 1]];

    for( var i = length - 2; i >= 0; i-- ) {
        if( characterMap[s[i]] < characterMap[s[i + 1]] ) {
            sum -= characterMap[s[i]];
        } else {
            sum += characterMap[s[i]];
        }
    }

    return sum;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

s = "MCMXCIV"
map<char, int> characterMap = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

length = s.length()
       = 7

Step 1: length == 0
        7 == 0
        false

Step 2: length == 1
        7 == 1
        false

Step 3: sum = characterMap[s[length - 1]]
            = characterMap[s[7 - 1]]
            = characterMap[s[6]]
            = characterMap['V']
            = 5

Step 4: for i = length - 2; i >= 0; i--
        i = 5
        5 >= 0

        characterMap[s[i]] < characterMap[s[i + 1]]
        characterMap[s[5]] < characterMap[s[6]]
        characterMap['I'] < characterMap['V']
        1 < 5
        true

        sum -= characterMap[s[i]]
             = characterMap[s[5]]
             = characterMap['I']
             = 1

        sum = 5 - 1
            = 4

        i--
        i = 4

Step 5: i >= 0
        i = 4
        4 >= 0

        characterMap[s[i]] < characterMap[s[i + 1]]
        characterMap[s[4]] < characterMap[s[5]]
        characterMap['C'] < characterMap['I']
        100 < 1
        false

        sum += characterMap[s[i]]
             = characterMap[s[4]]
             = characterMap['C']
             = 100

        sum = 4 + 100
            = 104

        i--
        i = 3

Step 6: i >= 0
        i = 3
        3 >= 0

        characterMap[s[i]] < characterMap[s[i + 1]]
        characterMap[s[3]] < characterMap[s[4]]
        characterMap['X'] < characterMap['C']
        10 < 100
        true

        sum -= characterMap[s[i]]
             = characterMap[s[3]]
             = characterMap['X']
             = 10

        sum = 104 - 10
            = 94

        i--
        i = 2

Step 7: i >= 0
        i = 2
        2 >= 0

        characterMap[s[i]] < characterMap[s[i + 1]]
        characterMap[s[2]] < characterMap[s[3]]
        characterMap['M'] < characterMap['X']
        1000 < 10
        false

        sum += characterMap[s[i]]
             = characterMap[s[2]]
             = characterMap['M']
             = 1000

        sum = 94 + 1000
            = 1094

        i--
        i = 1

Step 8: i >= 0
        i = 1
        1 >= 0

        characterMap[s[i]] < characterMap[s[i + 1]]
        characterMap[s[1]] < characterMap[s[2]]
        characterMap['C'] < characterMap['M']
        100 < 1000
        true

        sum -= characterMap[s[i]]
             = characterMap[s[1]]
             = characterMap['C']
             = 100

        sum = 1094 - 100
            = 994

        i--
        i = 0

Step 9: i >= 0
        i = 0
        0 >= 0

        characterMap[s[i]] < characterMap[s[i + 1]]
        characterMap[s[0]] < characterMap[s[1]]
        characterMap['M'] < characterMap['C']
        1000 < 100
        false

        sum += characterMap[s[i]]
             = characterMap[s[0]]
             = characterMap['M']
             = 100

        sum = 994 + 1000
            = 1994

        i--
        i = -1

Step 10: i >= 0
         i = -1
         -1 >= 0

return sum as 1994
Enter fullscreen mode Exit fullscreen mode

Top comments (0)