Solution by awice


  • 0

    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.


Log in to reply
 

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