Exploring LeetCode Problem 13: Roman to Integer — Python

Programming & Technical Interview Problems solved in Python

LeetCode Problem 13 Roman to Integer

Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid Roman numeral in the range [1, 3999].

Approach: Dictionary-Based Conversion

Our strategy for converting Roman numerals to integers hinges on the power of dictionaries. We utilize a carefully crafted dictionary to establish a clear and efficient mapping between Roman numeral symbols and their corresponding integer values. This approach allows us to navigate the intricacies of Roman numerals with grace and precision.

Solution

Step 1: Initializing the Roman Numeral Dictionary

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_numerals = {
          '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,
        }

Our journey into the world of Roman numeral conversion commences with a fundamental step: the initialization of the roman_numerals dictionary. This dictionary serves as our Rosetta Stone, bridging the gap between the elegance of Roman numeral symbols and the precision of integer values. Each key in the dictionary represents a Roman numeral symbol, while the corresponding value encapsulates its integer value.

Step 2: Initializing Variables

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_numerals = {
          '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,
        }

        answer = 0

        i = 0

• answer: This pivotal variable serves as the receptacle for the grand sum— the final integer value we seek to extract from the Roman numerals. As we traverse s, answer grows steadily, accumulating the contributions of each Roman numeral symbol.
• i: This pointer assumes the role of a cartographer. It keeps track of our position within the Roman numeral string, guiding us as we navigate its intricate twists and turns.

Step 3: Iterating Through the Roman Numeral String

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_numerals = {
          '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,
        }

        answer = 0

        i = 0

        while i < len(s):

            if i == len(s) - 1:
                answer += self.roman_numerals[s[i]]
                i += 1

            else:

                if s[i:i+2] in self.roman_numerals:
                    answer += self.roman_numerals[s[i:i+2]]
                    i += 2
                else:
                    answer += self.roman_numerals[s[i]]
                    i += 1

Checking for Valid Combinations: As we progress, we employ our roman_numerals dictionary to determine whether the current characters or their combinations form a valid Roman numeral symbol.

Updating the answer: Our actions depend on the outcome of this evaluation:

• If the current two characters (s[i:i+2]) align with a valid Roman numeral, we act decisively. We add the corresponding integer value to our ever-growing answer, signifying the successful translation of this Roman numeral symbol. In tandem, we take a stride of two positions forward along the string, marking our progress.
• If the current characters fail to form a valid Roman numeral, we adapt gracefully. Instead of frustration, we add the value of the current character (s[i]) to our answer. This character-by-character accumulation ensures that no symbol is left unaccounted for. With each step, we increment i by one, methodically exploring the Roman numeral string.

Step 4: Returning the Integer Equivalent

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_numerals = {
          '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,
        }

        answer = 0

        i = 0

        while i < len(s):

            if i == len(s) - 1:
                answer += self.roman_numerals[s[i]]
                i += 1

            else:

                if s[i:i+2] in self.roman_numerals:
                    answer += self.roman_numerals[s[i:i+2]]
                    i += 2
                else:
                    answer += self.roman_numerals[s[i]]
                    i += 1

        return answer

At this point, our final integer equivalent is stored in the answer variable which we can return outside of our while loop giving us the proper value of the converted roman numeral.

Time and Space Complexity

Time Complexity: O(n)

The cornerstone of our efficiency lies in our linear traversal through the input Roman numeral string s. At each step, we execute dictionary lookups and additions, all of which are performed in constant time.

This linear iteration, coupled with constant-time operations, ensures that the time complexity of our solution is O(n). Here, n signifies the length of the input Roman numeral string s. This linear relationship underscores our solution's ability to handle Roman numerals of varying lengths with grace and speed.

Space Complexity: O(1)

The heart of our solution lies in the roman_numerals dictionary, an entity with a fixed size. The dictionary's size remains constant, impervious to the length of the input Roman numeral string s.

Additionally, our solution’s variables (answer and i) are humble in their memory requirements, with no dependence on the input size.

As a result, the space complexity of our solution is a mere O(1). Regardless of the complexity or magnitude of the Roman numeral input, our memory footprint remains consistent and compact, a testament to efficient memory management.

Link to the problem:

https://leetcode.com/problems/roman-to-integer/