Gursehaj

Roman to Integer

Leetcode qs.13
Python code solution and explanation

question

Given a roman numeral, convert it to an integer.

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

Once you’ve understood the question, what we basically need to do is find a way to tell if each value in s is going to be added or subtracted. If a smaller value is before a bigger value, we subtract it from the total, instead of adding it.

For each value in s, if the current value is less than the next value, then subtract it from the total. Otherwise, add it. Now we can put that to code.

Here’s an example of what that might look like:

Solution

First, we need to identify each letter in s, and then assign a value. We can do this by using a hashmap.

        values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

total will be used to store the result. We will loop through i for the length of s amount of times.

        total = 0
        for i in range(len(s)):

We can take the value of s[i], which will equal the roman letter.  Now since we have a hashmap called values, we can simply wrap all this into values[s[i]], and this will equal the value of the roman letter. Let’s call values[s[i]] the current value. Likely, the value right next will be values[s[i + 1]]. Let’s call values[s[i + 1]], the next value. This is so we can make it easy to reference. Keep in mind, we are looping through i, so there will be a new current value and next value every time.

Now we need to check if the number is going to be added or subtracted (see previous logic). If the current value is less than the next value, then the current value will be subtracted from total. Else (if the current value is greater than the next value), then we will instead add the current value to total.

Also, there will be no next value if i + 1 is out of range (if it’s the last repetition). We can catch this by saying if i + 1 < len(s) AND the current value is less than the next value, only then subtract the current value from total. Otherwise, add the current value to total. If the current value is the last one in s, then it will always be added to total.

            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                total -= values[s[i]]
            else:
                total += values[s[i]]

After the loop is over, our end result will be saved to total. We can now return total. 

        return total
CODE
class Solution(object):
    def romanToInt(self, s):
        values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }
       
        total = 0
        for i in range(len(s)):
            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                total -= values[s[i]]
            else:
                total += values[s[i]]
       
        return total
Example Run

s = “MCDXIX” 

current value = 1000 (M), next value = 100 (C)
current value < next value = False  |  Add current value to total
total = 1000

current value = 100 (C), next value = 500 (D)
current value < next value = True |  Subtract current value from total
total = 900

current value = 500 (D), next value = 10 (X)
current value < next value = False  |  Add current value to total
total = 1400

current value = 10 (X), next value = 1 (I)
current value < next value = False  |  Add current value to total
total = 1410

current value = 1 (I), next value = 10 (X)
current value < next value = True |  Subtract current value from total
total = 1409

i + 1 < len(s) = False
Add current value (10) to total
total = 1419

return total (1419)

Conclusion

By thinking about what exactly the question was asking us, we were able to come up with a very easy and efficient solution. The program was basically about whether to add or subtract the current value, by comparing the current value and next value. The time complexity was O(n), where n was the length of s. There was a little extra memory used, just the hashmap.

Gursehaj

,