###### 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
```
Sign in with Wallet
Connect another wallet