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.