Welcome to Subscribe On Youtube

Question

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

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

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

Algorithm

I-1

V-5

X-10

L-50

C-100

D-500

M-1000
  1. The same number is written consecutively, the number represented is equal to the number obtained by adding these numbers, such as: Ⅲ = 3;
  2. 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;
  3. 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;
  4. 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)
  5. 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:

  1. 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.
  2. 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.
  3. The small numbers to the left of V and X can only use .
  4. The small numbers to the left of L and C can only be X.
  5. 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:

  1. If the current number is the last number or the following number is smaller than it, add the current number to the total sum.
  2. 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

  • 
    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];
            }
        }
    }
    
    ############
    
    class Solution {
        public int romanToInt(String s) {
            Map<String, Integer> nums = new HashMap<>();
            nums.put("M", 1000);
            nums.put("CM", 900);
            nums.put("D", 500);
            nums.put("CD", 400);
            nums.put("C", 100);
            nums.put("XC", 90);
            nums.put("L", 50);
            nums.put("XL", 40);
            nums.put("X", 10);
            nums.put("IX", 9);
            nums.put("V", 5);
            nums.put("IV", 4);
            nums.put("I", 1);
            int res = 0;
            for (int i = 0; i < s.length();) {
                if (i + 1 < s.length() && nums.get(s.substring(i, i + 2)) != null) {
                    res += nums.get(s.substring(i, i + 2));
                    i += 2;
                } else {
                    res += nums.get(s.substring(i, i + 1));
                    i += 1;
                }
            }
            return res;
        }
    }
    
  • // 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
    
    
  • func romanToInt(s string) int {
    	romans := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    	ans := 0
    	for i := 0; i < len(s)-1; i++ {
    		if romans[s[i]] < romans[s[i+1]] {
    			ans -= romans[s[i]]
    		} else {
    			ans += romans[s[i]]
    		}
    	}
    	return ans + romans[s[len(s)-1]]
    }
    
  • const romanToInt = function (s) {
        const map = {
            I: 1,
            V: 5,
            X: 10,
            L: 50,
            C: 100,
            D: 500,
            M: 1000,
        };
        let sum = 0;
        for (let i = 0; i < s.length; i++) {
            if (map[s[i]] < map[s[i + 1]]) {
                sum -= map[s[i]];
            } else {
                sum += map[s[i]];
            }
        }
        return sum;
    };
    
    
  • # @param {String} s
    # @return {Integer}
    def roman_to_int(s)
      hash = Hash[
          'I' => 1,
          'V' => 5,
          'X' => 10,
          'L' => 50,
          'C' => 100,
          'D' => 500,
          'M' => 1000,
          'IV' => 4,
          'IX' => 9,
          'XL' => 40,
          'XC' => 90,
          'CD' => 400,
          'CM' => 900
      ]
      res = 0
      i = 0
      while i < s.length
        if i < s.length - 1 && !hash[s[i..i+1]].nil?
          res += hash[s[i..i+1]]
          i += 2
        else
          res += hash[s[i]]
          i += 1
        end
      end
    
      res
    end
    
    
  • class Solution {
        /**
         * @param String $s
         * @return Integer
         */
        function romanToInt($s) {
            $hashmap = array('I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100, 'D' => 500, 'M' => 1000);
            $rs = 0;
            for ($i = 0; $i < strlen($s); $i++) {
                $left = $hashmap[$s[$i]];
                $right = $hashmap[$s[$i + 1]];
                if ($left >= $right) $rs += $left;
                else $rs -= $left;
            }
            return $rs;
        }
    }
    
  • function romanToInt(s: string): number {
        const d: Map<string, number> = new Map([
            ['I', 1],
            ['V', 5],
            ['X', 10],
            ['L', 50],
            ['C', 100],
            ['D', 500],
            ['M', 1000],
        ]);
        let ans: number = d.get(s[s.length - 1])!;
        for (let i = 0; i < s.length - 1; ++i) {
            const sign = d.get(s[i])! < d.get(s[i + 1])! ? -1 : 1;
            ans += sign * d.get(s[i])!;
        }
        return ans;
    }
    
    
  • public class Solution {
        public int RomanToInt(string s) {
            Dictionary<char, int> d = new Dictionary<char, int>();
            d.Add('I', 1);
            d.Add('V', 5);
            d.Add('X', 10);
            d.Add('L', 50);
            d.Add('C', 100);
            d.Add('D', 500);
            d.Add('M', 1000);
            int ans = d[s[s.Length - 1]];
            for (int i = 0; i < s.Length - 1; ++i) {
                int sign = d[s[i]] < d[s[i + 1]] ? -1 : 1;
                ans += sign * d[s[i]];
            }
            return ans;
        }
    }
    

All Problems

All Solutions