Question

Formatted question description: https://leetcode.ca/all/13.html

 13	Roman to Integer

 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
 For example, two is written as II in Roman numeral, just two one's added together.
 Twelve is written as, XII, which is simply X + II.
 The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

 Example 1:

 Input: "III"
 Output: 3

 Example 2:

 Input: "IV"
 Output: 4

 Example 3:

 Input: "IX"
 Output: 9

 Example 4:

 Input: "LVIII"
 Output: 58
 Explanation: L = 50, V= 5, III = 3.

 Example 5:

 Input: "MCMXCIV"
 Output: 1994
 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 @tag-string

Algorithm

I-1

V-5

X-10

L-50

C-100

D-500

M-1000

The same number is written consecutively, the number represented is equal to the number obtained by adding these numbers, such as: Ⅲ = 3;
The small number is on the right side of the big number, and the number represented is equal to the number obtained by adding these numbers, such as: Ⅷ = 8; Ⅻ = 12;
Small numbers (limited to Ⅰ, X, and C) are on the left side of large numbers, and the number represented is equal to the number obtained by reducing the large number, such as: Ⅳ = 4; Ⅸ = 9;
In normal use, the consecutive number shall not be repeated more than three times. (The four o’clock “IIII” on the dial is an exception)
Draw a horizontal line on top of a number, which means that the number is expanded 1000 times.

There are a few things to be aware of:

Any one of the basic numbers Ⅰ, X, and C can not exceed three if it is used to form a number by itself or is placed on the right side of a large number; only one can be used on the left side of a large number.
You can’t put any of the basic numbers V, L, D as a decimal number on the left side of the large number and use subtraction to form the number; put it on the right side of the large number and use the addition method to form the number, only one can be used.
The small numbers to the left of V and X can only use Ⅰ.
The small numbers to the left of L and C can only be X.
Only C can be used for the small numbers on the left of D and M.

To solve this problem, we can use a HashMap data structure to convert the letters of the Roman numerals into the corresponding integer values. Since the input must be a Roman numeral, we can assume two cases:

If the current number is the last number or the following number is smaller than it, add the current number to the total sum.
In other cases, subtract the current number from the total sum.

We can iterate through the input string and add or subtract the corresponding integer values based on these rules. At the end of the iteration, we will have the total sum of the Roman numeral.

Code

Java

public class Roman_to_Integer {
    class Solution {
        public int romanToInt(String s) {


            // pre-process array
            int nums[] = new int[s.length()];
            for (int i = 0; i < s.length(); i++) {
                switch (s.charAt(i)) {
                    case 'M':
                        nums[i] = 1000;
                        break;
                    case 'D':
                        nums[i] = 500;
                        break;
                    case 'C':
                        nums[i] = 100;
                        break;
                    case 'L':
                        nums[i] = 50;
                        break;
                    case 'X':
                        nums[i] = 10;
                        break;
                    case 'V':
                        nums[i] = 5;
                        break;
                    case 'I':
                        nums[i] = 1;
                        break;
                }
            }

            // sum up
            int sum = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] < nums[i + 1]) {
                    sum -= nums[i];
                } else {
                    sum += nums[i];
                }
            }
            return sum + nums[nums.length - 1];
        }
    }
}

// OJ: https://leetcode.com/problems/roman-to-integer/
// Time: O(N)
// Space: O(1)
class Solution {
private:
    int charToNum(char c) {
        switch(c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
        }
        return 0;
    }
public:
    int romanToInt(string s) {
        int ans = 0, last = INT_MAX;
        for (char c : s) {
            int n = charToNum(c);
            if (n > last) ans -= 2 * last;
            ans += n;
            last = n;
        }
        return ans;
    }
};

class Solution:
    def romanToInt(self, s: str) -> int:
        romans = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        ans = 0
        for i in range(len(s) - 1):
            if romans[s[i]] < romans[s[i + 1]]:
                ans -= romans[s[i]]
            else:
                ans += romans[s[i]]
        return ans + romans[s[-1]]

############

class Solution(object):
  def romanToInt(self, s):
    """
    :type s: str
    :rtype: int
    """
    d = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    ans = 0
    for i in range(0, len(s) - 1):
      c = s[i]
      cafter = s[i + 1]
      if d[c] < d[cafter]:
        ans -= d[c]
      else:
        ans += d[c]
    ans += d[s[-1]]
    return ans

13 - Roman to Integer

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions