#13

Easy

LeetCode Problem Workspace

Roman to Integer

Convert a Roman numeral string into an integer using a hash table and mathematical principles to determine value order.

Problem Statement

Roman numerals are written with seven distinct symbols: I, V, X, L, C, D, and M. Each symbol has a corresponding integer value, and numerals are typically written from largest to smallest. However, when a smaller numeral precedes a larger one, like in IV for 4 or IX for 9, the value is subtracted. Your task is to convert a given Roman numeral string into its equivalent integer.

Given that Roman numerals are valid within the range from 1 to 3999, the solution should consider each numeral and determine whether to add or subtract its value based on the numeral before it. A hash table can be used to map the Roman symbols to their integer values for efficient lookup, and the problem can be solved by iterating over the string from back to front.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Example 2

Input: s = "III"

Output: 3

III = 3.

Example 3

Input: s = "LVIII"

Output: 58

L = 50, V= 5, III = 3.

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].

Solution Approach

Use a Hash Table for Symbol Values

Map each Roman numeral symbol (I, V, X, etc.) to its corresponding integer value using a hash table. This allows O(1) time complexity for retrieving the value of any symbol in the string.

Iterate Backwards Through the String

By iterating through the string from right to left, we can easily handle subtraction cases. If a smaller numeral appears before a larger one (e.g., I before V), subtract the smaller numeral's value from the total. Otherwise, add it.

Consider Edge Cases

Special cases like 'IV', 'IX', 'XL', 'XC', 'CD', and 'CM' should be handled by checking if a smaller numeral precedes a larger one. The algorithm needs to efficiently account for these rules while maintaining linear time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n), where n is the length of the Roman numeral string. This is because we iterate through the string once. The space complexity is O(1) as the hash table contains a fixed number of elements (seven symbols), which does not depend on the input size.

What Interviewers Usually Probe

Do you understand how the subtraction rule works in Roman numerals?
Can you efficiently solve the problem using both a hash table and mathematical principles?
Will you be able to handle edge cases like 'IX' or 'CM' during the interview?

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the subtraction rule, such as treating 'IV' as 'IIII' or incorrectly handling cases like 'IX'.
Failing to account for the correct direction in which to iterate through the string, leading to errors in subtraction logic.
Not properly using the hash table, which could result in inefficient symbol lookups or errors in mapping values.

Follow-up variants

Convert a Roman numeral string to an integer using a recursive approach.
Extend the solution to support Roman numerals in the range from 1 to 5000.
Implement an optimized version of the solution that minimizes space complexity.

FAQ

How do you handle subtraction rules in Roman numerals for this problem?

By checking if a smaller numeral precedes a larger one in the string, like 'IV' for 4 or 'IX' for 9, and applying subtraction accordingly.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of the string, as the algorithm processes each symbol once.

What are the main trade-offs in solving this problem efficiently?

The trade-off is between clarity and efficiency: using a hash table ensures O(1) lookups but requires handling subtraction rules carefully during iteration.

Can this problem be solved using recursion?

Yes, recursion can be applied, but the iterative approach with a hash table tends to be simpler and more efficient for this problem.

How would the solution change if Roman numerals were extended beyond 3999?

Extending Roman numerals would require changes to the hash table and possibly more complex subtraction rules for larger values.

terminal

Solution

Solution 1: Hash Table + Simulation

First, we use a hash table $d$ to record the numerical value corresponding to each character. Then, we traverse the string $s$ from left to right. If the numerical value corresponding to the current character is less than the numerical value corresponding to the character on the right, we subtract the numerical value corresponding to the current character. Otherwise, we add the numerical value corresponding to the current character.

1

2

3

4

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        return sum((-1 if d[a] < d[b] else 1) * d[a] for a, b in pairwise(s)) + d[s[-1]]

Continue Practicing

#12 integer to roman #166 fraction to recurring decimal #770 basic calculator iv