13. Roman to Integer
Model: qwen2.5-coder:14b
Topics: Math,String
FAANG asked: 1
Acceptance rate: 57.0%
Problem Breakdown
The problem requires converting a Roman numeral string into its corresponding integer value. The input is a string s containing only valid Roman numeral characters (I, V, X, L, C, D, M). The output should be an integer representing the numeric value of the Roman numeral.
Inputs:
- A string
s(1 <= s.length <= 15) containing Roman numerals.
Outputs:
- An integer representing the numeric value of the Roman numeral.
Implicit Constraints and Edge Cases:
- The input is guaranteed to be a valid Roman numeral.
- The Roman numeral will always represent a number between 1 and 3999.
- There are specific cases where subtraction is used (e.g.,
IVfor 4,IXfor 9).
Intuition
The brute-force approach would involve checking each possible combination of Roman numerals to determine their values. However, this approach is inefficient due to its high time complexity and unnecessary checks.
A better approach involves recognizing that in a valid Roman numeral:
- If a smaller numeral appears before a larger numeral (e.g.,
IV), it indicates subtraction. - Otherwise, the numerals are added together.
The key insight is to iterate through the string from left to right. This allows us to easily determine whether to add or subtract each numeral based on its position relative to the next numeral.
Approach
-
Mapping Roman Numerals to Values:
- Create a dictionary that maps each Roman numeral character to its corresponding integer value.
-
Iterate Through the String from Left to Right:
- Initialize a variable
totalto store the resulting integer. - Iterate through the string
sfrom left to right. - For each character, check if its value is less than the next numeral’s value:
- If true, subtract its value from
total. - If false, add its value to
total.
- If true, subtract its value from
- Initialize a variable
-
Return the Result:
- After processing all characters, return the
totalas the integer representation of the Roman numeral.
- After processing all characters, return the
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string
s. We iterate through the string once. - Space Complexity: O(1). The space used does not depend on the size of the input, only a fixed amount of extra space for variables and the dictionary.
Solution
def romanToInt(s: str) -> int:
# Mapping of Roman numerals to their integer values
roman_to_value = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
total = 0
prev_value = 0
# Iterate through the string from left to right
for char in s:
current_value = roman_to_value[char]
if current_value > prev_value:
total -= prev_value * 2
total += current_value
prev_value = current_value
return total
Edge Cases Handled
- Single Character Roman Numerals: The algorithm correctly handles single-character inputs like
I,V, etc. - Subtractive Combinations: The algorithm correctly processes subtractive combinations such as
IV(4),IX(9),XL(40),XC(90),CD(400), andCM(900). - Maximum Value: The algorithm can handle the maximum possible Roman numeral,
MMMCMXCIX, which equals 3999.