---
# System prepended metadata

title: 13. Roman to Integer
tags: [leetcode]

---

###### tags: `leetcode`
# 13. Roman to Integer
## My 1st idea
### Use dictionary
ref = https://en.wikibooks.org/wiki/A-level_Computing/AQA/Paper_1/Fundamentals_of_data_structures/Dictionaries
### try - fail
```python=
def function(s):
    myDict = {'I':1, 'V': 5, 'X': 10,'L': 50, 'C': 100,'D': 500,'M': 1000}
    cur = 0  # current
    ct = 0  # counter
    sum = 0
    # Use a style of not changing the input data
    while ct <= len(s):
        if myDict(s[len(s) - ct]) <= cur:
            sum += myDict(s[len(s) - ct])
        else:
            sum -= myDict(s[len(s) - ct])
            curr = 0
        ct += 1
    return sum
```
:::danger
s[len(s) - ct]
index out of range
:::
### try - fail
```python=
class Solution:
    def romanToInt(self, s: str) -> int:
        myDict = {'I':1, 'V': 5, 'X': 10,'L': 50, 'C': 100,'D': 500,'M': 1000}
        cur = 0  # current
        ct = 0  # counter
        sum = 0
        # Use a style of not changing the input data
        while len(s) - 1 - ct >= 0:
            if myDict(s[len(s) - 1 - ct]) <= cur:
                sum += myDict(s[len(s) - 1 - ct])
            else:
                sum -= myDict(s[len(s) - 1 - ct])
                curr = 0
            ct =+ 1
        return sum
```
:::danger
TypeError: 'dict' object is not callable
:::
### try - fail
```python=
class Solution:
    def romanToInt(self, s: str) -> int:
        myDict = {'I':1, 'V': 5, 'X': 10,'L': 50, 'C': 100,'D': 500,'M': 1000}
        cur = 0  # current
        ct = 0  # counter
        sum = 0
        # Use a style of not changing the input data
        while len(s) - 1 - ct >= 0:
            if myDict[s[len(s) - 1 - ct]] <= cur:
                sum += myDict[s[len(s) - 1 - ct]]
            else:
                sum -= myDict[s[len(s) - 1 - ct]]
                curr = 0
            ct =+ 1
        return sum
```
:::danger
Time Limit Exceeded
:::

:::warning
ct =+ 1
ct += 1
:::
### try - fail
```python=
class Solution:
    def romanToInt(self, s: str) -> int:
        myDict = {'I':1, 'V': 5, 'X': 10,'L': 50, 'C': 100,'D': 500,'M': 1000}
        cur = 0  # current
        ct = 0  # counter
        sum = 0
        # Use a style of not changing the input data
        while len(s) - 1 - ct >= 0:
            if myDict[s[len(s) - 1 - ct]] <= cur:
                sum += myDict[s[len(s) - 1 - ct]]
            else:
                sum -= myDict[s[len(s) - 1 - ct]]
                curr = 0
            ct += 1
        return sum
```
:::danger
Wrong Answer
Runtime: 60 ms
Your input
"III"
Output
-3
Expected
3
:::
### try - success
```python=
class Solution:
    def romanToInt(self, s: str) -> int:
        myDict = {'I':1, 'V': 5, 'X': 10,'L': 50, 'C': 100,'D': 500,'M': 1000}
        cur = 0  # current
        ct = 0  # counter
        sum = 0
        # Use a style of not changing the input data
        while len(s) - 1 - ct >= 0:
            if myDict[s[len(s) - 1 - ct]] >= cur:
                cur = myDict[s[len(s) - 1 - ct]]
                sum += cur
            else:
                sum -= myDict[s[len(s) - 1 - ct]]
                curr = 0
            ct += 1
        return sum
```
:::success
Accepted
Runtime: 60 ms
Your input
"III"
Output
3
Expected
3
:::
:::info
Success
Details
Runtime: 52 ms, faster than 80.23% of Python3 online submissions for Roman to Integer.
Memory Usage: 14 MB, less than 5.38% of Python3 online submissions for Roman to Integer.
:::
## another person's
I didn't realized that there are only 6 cases of subtraction.
```java=
public int romanToInt(String s) {
     int sum=0;
    if(s.indexOf("IV")!=-1){sum-=2;}
    if(s.indexOf("IX")!=-1){sum-=2;}
    if(s.indexOf("XL")!=-1){sum-=20;}
    if(s.indexOf("XC")!=-1){sum-=20;}
    if(s.indexOf("CD")!=-1){sum-=200;}
    if(s.indexOf("CM")!=-1){sum-=200;}
    
    char c[]=s.toCharArray();
    int count=0;
    
   for(;count<=s.length()-1;count++){
       if(c[count]=='M') sum+=1000;
       if(c[count]=='D') sum+=500;
       if(c[count]=='C') sum+=100;
       if(c[count]=='L') sum+=50;
       if(c[count]=='X') sum+=10;
       if(c[count]=='V') sum+=5;
       if(c[count]=='I') sum+=1;
   }
   return sum;
}
```
## another person's
Unordered_map, ref = https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/

It is implemented by hash table.

The same way as mine.
Starting from `int sum = T[s.back()];`.
Not use `current`.

If using `T[s[i]] < T[s[i + 1]]`,  
at the tail end of the string, the last element will have to compare with something outside the string.  
So, this person's method is really educational.
```cpp=
int romanToInt(string s) 
{
    unordered_map<char, int> T = { { 'I' , 1 },
                                   { 'V' , 5 },
                                   { 'X' , 10 },
                                   { 'L' , 50 },
                                   { 'C' , 100 },
                                   { 'D' , 500 },
                                   { 'M' , 1000 } };
   int sum = T[s.back()];
   for (int i = s.length() - 2; i >= 0; --i) 
   {
       if (T[s[i]] < T[s[i + 1]])
       {
           sum -= T[s[i]];
       }
       else
       {
           sum += T[s[i]];
       }
   }
   
   return sum;
}
```
## another person's
Why its index will not go out of range?? I mean `if roman[s[i]] < roman[s[i+1]]:`.  
Oh!Oh!Oh!   
I now understand.  
And it has `return z + roman[s[-1]]`, which is really smart!!!  
Since the last Roman Character is always positive.
```python=
class Solution:
# @param {string} s
# @return {integer}
def romanToInt(self, s):
    roman = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
    z = 0
    for i in range(0, len(s) - 1):
        if roman[s[i]] < roman[s[i+1]]:
            z -= roman[s[i]]
        else:
            z += roman[s[i]]
    return z + roman[s[-1]]
```
## another person's
I like `for i in s[::-1]:`.
Use it, and I will never have mistakes on reversed for-loop.
```python=
def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        _dict = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        prev = 0
        sum = 0
        for i in s[::-1]:
            curr = _dict[i]
            if prev > curr:
                sum -= curr
            else:
                sum += curr
            prev = curr
        return sum
```
## another person's
Easy to track what is the Roman character now.
```python=
d = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}

def romanToInt(self, s):
    res, p = 0, 'I'
    for c in s[::-1]:
        res, p = res - d[c] if d[c] < d[p] else res + d[c], c
    return res
```

