LeetCode #13 Roman to Integer Solution & Explanation

Content

Post Views: 1,468

LeetCode Problem

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

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.

Solution

First, let us look at the six instances, they are important for solving this problem.

We can find that number 4 and 9 will cause the special situations.

Normally, Roman numeral letters sort from large to small, but in special situations, it will not.

C# Solution

Solution1

public class Solution {
    private readonly Dictionary<char, int> dict = 
new Dictionary<char, int>{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    
    public int RomanToInt(string s) {
   
        char[] ch = s.ToCharArray();
    
        int result = 0;
        int intVal,nextIntVal;
            
        for(int i = 0; i <ch.Length ; i++){
            intVal = dict[ch[i]];
            
            if(i != ch.Length-1)
            {
                nextIntVal = dict[ch[i+1]];
                
                if(nextIntVal>intVal){
                    intVal = nextIntVal-intVal;
                    i = i+1;
                }
            }
             result = result + intVal;
        }
        return result;
    }
}

We can see if the next number is greater than the recent number, it means that it is a special situation if(nextIntVal>intVal) ➡ so recent number should be subtracted not added, and i = i+1 ➡ next number will be added this time and will skip to the number after it.

Solution2

public class Solution {
    private readonly Dictionary<char, int> dict = 
new Dictionary<char, int>{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    
    public int RomanToInt(string s) {
        
        //special situations
        s = s.Replace("IV","IIII");
        s = s.Replace("IX","VIIII");
        s = s.Replace("XL","XXXX");
        s = s.Replace("XC","LXXXX");
        s = s.Replace("CD","CCCC");
        s = s.Replace("CM","DCCCC");
        
        int result = 0;
        
        foreach(var ch in s)
        {
            result += dict[ch];
        }
        
        return result;
    }
}

Replace the special situations, and just run an easy iteration and sum the numbers. Just that simple !

Java Solution

Solution1 (use map to store ➡ similar to C# dictionary )

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>() {{
        
            put('I',1);
            put('V',5);
            put('X',10);
            put('L',50);
            put('C',100);
            put('D',500);
            put('M',1000);
            
        }};
        
        char[] arr = s.toCharArray();
        
        int result = 0;
        int intVal,nextIntVal;
            
        for(int i = 0; i <arr.length ; i++){
            intVal = map.get(arr[i]);
            
            if(i != arr.length-1)
            {
                nextIntVal = map.get(arr[i+1]);
                
                if(nextIntVal>intVal){
                    intVal = nextIntVal-intVal;
                    i = i+1;
                }
            }
             result = result + intVal;
        }
        return result;
    }
}

⭐Runtime : 9ms、9ms、12ms ➡ average 10 ms

Solution2

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>() {{
        
            put('I',1);
            put('V',5);
            put('X',10);
            put('L',50);
            put('C',100);
            put('D',500);
            put('M',1000);
            
        }};
        
        //special situations  
        s = s.replace("IV","IIII");
        s = s.replace("IX","VIIII");
        s = s.replace("XL","XXXX");
        s = s.replace("XC","LXXXX");
        s = s.replace("CD","CCCC");
        s = s.replace("CM","DCCCC");
        
        
        int result = 0;
        for (char ch: s.toCharArray()) {
            result+= map.get(ch);
        }
        
        return result;
    }
}

Runtime : 14ms、20ms、14ms ➡ average 16 ms

Python3 Solution

Solution1

class Solution:
    def romanToInt(self, s: str) -> int:
       dict = {
        'I' : 1,
        'V' : 5,
        'X' : 10,
        'L' : 50,
        'C' : 100,
        'D' : 500,
        'M' : 1000
        } 
       result  = 0
       tmp = 0;
       i = 0

       while i < len(s):
           tmp = dict[s[i]];
           if (i +1) < len(s) and dict[s[i]] < dict[s[i + 1]]:
               tmp = dict[s[i + 1]] - dict[s[i]]
               i += 1
           i += 1
           result += tmp;

       return (result)

Solution2

class Solution:
    def romanToInt(self, s: str) -> int:
       dict = {
        'I' : 1,
        'V' : 5,
        'X' : 10,
        'L' : 50,
        'C' : 100,
        'D' : 500,
        'M' : 1000
        } 
       s = s.replace("IV","IIII").replace("IX","VIIII");
       s = s.replace("XL","XXXX").replace("XC","LXXXX");
       s = s.replace("CD","CCCC").replace("CM","DCCCC");
      
       result = 0;
       for i in range(len(s)):
           result += dict[s[i]];          


       return (result)

JavaScript Solution

Solution1 (use dictionary and next Roman numeral to check add or subtract)

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var dict = {
      'I':1,
      'V':5,
      'X':10,
      'L':50,
      'C':100,
      'D':500,
      'M':1000
    };
    
    var result = 0;
    var intVal = 0;
    var nextIntVal = 0;
    for (var i = 0; i < s.length; i++) {
        intVal = dict[s[i]];
        
        if(i!=s.length-1)
        {
            nextIntVal = dict[s[i+1]];
            if(nextIntVal>intVal){
                intVal = nextIntVal-intVal;
                i = i+1;
            }
        }
        result = result + intVal;
    }
    return result;
};

Test Runtime – 208 ms, faster than 35.78% 、172 ms, faster than 60.74% 、195 ms, faster than 45.00% ➡ average 192 ms

Solution2 (replace special situations)

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var dict = {
      'I':1,
      'V':5,
      'X':10,
      'L':50,
      'C':100,
      'D':500,
      'M':1000
    };
    
    s = s.replace("IV","IIII").replace("IX","VIIII");
    s = s.replace("XL","XXXX").replace("XC","LXXXX");
    s = s.replace("CD","CCCC").replace("CM","DCCCC");
    
    var result = 0;

    for (var i = 0; i < s.length; i++) {
        result+=dict[s[i]];
    }
    return result;
};

Test Runtime – 201 ms, faster than 40.72% 、140 ms, faster than 80.10% 、183 ms, faster than 53.61%

➡ average 175 ms

Conclusion

This problem is the first problem I solved in LeetCode, and I took a while to find out the answer.

After some optimization, now the running speed seems just ok.

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot!

"I came, I saw, I conquered."
                                                                                                                 Julius Caesar

Hope everyone can come, see, and conquer.

Cover Photo – Photo by Karl Callwood on Unsplash

The problem link : Roman to Integer – LeetCode

See Next Problem : LeetCode #14 Longest Common Prefix Solution & Explanation – zyrastory Code & Food Research Center

Technology Post

Random post

Abhishek
2022-06-16 / 12:45 pm Reply
dict = {
‘I’ : 1,
‘V’ : 5,
‘X’ : 10,
‘L’ : 50,
‘C’ : 100,
‘D’ : 500,
‘M’ : 1000
}
result = 0
tmp = 0;
i = 0
while i < len(s):
tmp = dict[s[i]];
if (i +1) < len(s) and dict[s[i]] < dict[s[i + 1]]:
tmp = dict[s[i + 1]] – dict[s[i]]
i += 1
i += 1
result += tmp;
return (result)
I gave the input as IV.
Now when the len(s) =2 so when i=1 in the second iteration shouldn't "dict[s[i]] < dict[s[i + 1]]" this give an IndexError: string index out of range? since s[2] doesn't exist?
- zyrastory
  2022-06-16 / 2:03 pm Reply
  I think you are talking about the solution1 of Python3 code!
  Sure, s[2] doesn’t exist, because the len of IV is 2.
  But in this case i will add i+=1 after the condition 【if (i +1) < len(s) and dict[s[i]] < dict[s[i + 1]]:】 >> 【(0+1)<1 and 1<5】➡ i=1
  And out of the if condition, it will be add again ➡ i=2
  So in this case, the next iteration will be break 【while i < len(s):】 >> 【2<2】will get false and break!
  The IndexError will not happen in this case.
  Hope the explanation helps you !
Gurbakshish
2022-12-02 / 10:47 am Reply
var romanToInt = function(s) {
const dict = {
‘I’:1,
‘V’:5,
‘X’:10,
‘L’:50,
‘C’:100,
‘D’:500,
‘M’:1000
};
var result = 0;
var intVal = 0;
var nextIntVal = 0;
for(i = 0; i < s.length; i++) {
intVal = dict[s[i]];
if(i != s.length – 1) {
if(nextIntVal<intVal) {
nextIntVal = dict[s[i+1]];
intVal = intVal – nextIntVal;
i = i + 1;
}
}
result = result + intVal;
}
return result;
};

LeetCode Problem

Solution

C# Solution

Java Solution

Python3 Solution

JavaScript Solution

Conclusion

LeetCode #35 Search Insert Position Solution & Explanation

LeetCode #507 Perfect Number Solution & Explanation

LeetCode #5 Longest Palindromic Substring Solution & Explanation

LeetCode #231 Power of Two Solution & Explanation

LeetCode #88 Merge Sorted Array Solution & Explanation

LeetCode #50 Pow(x, n) Solution & Explanation

3 Comments

Leave a ReplyCancel Reply

LeetCode Problem

Solution

C# Solution

Java Solution

Python3 Solution

JavaScript Solution

Conclusion

Related Posts

3 Comments

Leave a ReplyCancel Reply