# Solution by awice

• #### Approach #1: Parsing Tokens [Accepted]

Intuition

If say, `S = 'MMLXV'`, then the answer would be `'M' (1000)` plus the answer for `S = 'MLXV'`. Our idea is to add the answer from left to right, parsing the tokens as we go.

Algorithm

We repeatedly remove the largest token representing a value, and add that value to our answer. For example, if we have `S = 'LXV'`, we will remove `'L'` for `ans += 50`, then `'X'` for `ans += 10`, and finally `'V'` for `ans += 5`.

However, for a string like `S = 'XL'`, the answer is `40`, not `60`. We can repair our initial idea by using not just tokens like `'M', 'D', 'C', 'L', 'X', 'V', 'I'`, but also tokens like `'CM', 'CD, 'XC', 'XL', 'IX', 'IV'`.

Python

``````class Solution(object):
def romanToInt(self, S):
tokens = [('M', 1000), ('CM', 900), ('D', 500), ('CD', 400),
('C', 100), ('XC', 90), ('L', 50), ('XL', 40),
('X', 10), ('IX', 9), ('V', 5), ('IV', 4), ('I', 1)]
ans = i = 0
for token, value in tokens:
while S[i: i+len(token)] == token:
i += len(token)
ans += value
return ans
``````

Complexity Analysis

• Time Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is the length of the string. We must process every token of the string.

• Space Complexity: \$\$O(N)\$\$. Only a constant amount of space is used to store the answer, but intermediate strings `S[i: i+len(token)]` take up \$\$O(N)\$\$ space.

#### Approach #2: Determine The Sign Of Each Token [Accepted]

Intuition

In looking at `S = 'LX' (50 + 10)` versus `S = 'XL' (-10 + 50)`, based on the relative position of the primary tokens `'M', 'D', 'C', 'L', 'X', 'V', 'I'`, their signed contribution is either positive or negative.

Algorithm

To know whether each token contributes positively or negatively, we simply check if it's right neighbor is larger. If it is, then it contributed negatively. Otherwise, it contributed positively.

Python

``````class Solution(object):
def romanToInt(self, S):
tokens = {'M': 1000, 'D': 500, 'C': 100, 'L': 50,
'X': 10, 'V': 5, 'I': 1}
ans = 0

for i, c in enumerate(S):
val = tokens[c]
if i+1 < len(S) and tokens[S[i+1]] > val:
ans -= val
else:
ans += val
return ans
``````

Complexity Analysis

• Time Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is the length of the string. We must process every token of the string.

• Space Complexity: \$\$O(1)\$\$. Only a constant amount of space is used to store the answer.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.