Leetcode Study Day 9

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

My solution and the improved one

My first idea is set a lot of if statements to deal with different roman letter. It doesn’t cost extra space but the code seems redundant.

The improved solution is create an unordered_map first. Then we find the pattern that if the current letter is smaller than the next one, it means this situation happened:

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.

So we minus the current letter from the result. Otherwise, we add the current letter to the result.

Full Code

class Solution {
public:
    int romanToInt(string s) {
        unordered_map <char, int> romanMap;
        romanMap['I'] = 1;
        romanMap['V'] = 5;
        romanMap['X'] = 10;
        romanMap['L'] = 50;
        romanMap['C'] = 100;
        romanMap['D'] = 500;
        romanMap['M'] = 1000;
        int answer = 0;
        for (int i = 0; i < s.size(); i++){
            if (romanMap[s[i]] >= romanMap[s[i+1]])
                answer += romanMap[s[i]];
            else
                answer -= romanMap[s[i]];
        }
        return answer;
    }
};

Integer to Roman

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 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 an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.
Example 2:

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

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

1 <= num <= 3999

Solution

I create a vector with pairs, in each pair it contains the value and its corresponding string. Then I iterate the vector from the largest value to the smallest value. while the current num, which is the input, is larger or equal than the value, we add the corresponding string to the answer, and update the num by minusing the value. Otherwise, we move to the next pair.

class Solution {
public:
    string intToRoman(int num) {
        vector <pair<int, string>> romanMap;
        romanMap.push_back(make_pair(1000,"M"));
        romanMap.push_back(make_pair(900,"CM"));
        romanMap.push_back(make_pair(500,"D"));
        romanMap.push_back(make_pair(400,"CD"));
        romanMap.push_back(make_pair(100,"C"));
        romanMap.push_back(make_pair(90, "XC"));
        romanMap.push_back(make_pair(50,"L"));
        romanMap.push_back(make_pair(40,"XL"));
        romanMap.push_back(make_pair(10,"X"));
        romanMap.push_back(make_pair(9,"IX"));
        romanMap.push_back(make_pair(5,"V"));
        romanMap.push_back(make_pair(4, "IV"));
        romanMap.push_back(make_pair(1,"I"));

        string answer = "";

        for (const auto& pair : romanMap) {
            while (num >= pair.first) {
                answer += pair.second;
                num = num - pair.first;
            }
        }

        return answer;
    }
};