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.

#13

Easy

auto_awesome哈希·数学

LeetCode 题解工作台

罗马数字转整数

罗马数字包含以下七种字符: I ， V ， X ， L ， C ， D 和 M 。字符数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如，罗马数字 2 写做 II ，即为两个并列的 1 。 12 写做 XII ，即为 X + II 。 27 写做 XXVII …

哈希表数学字符串

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - 百度百科。

lightbulb

解题思路

方法一：哈希表 + 模拟

我们先用哈希表 $d$ 记录每个字符对应的数值，然后从左到右遍历字符串 $s$ ，如果当前字符对应的数值小于右边字符对应的数值，则减去当前字符对应的数值，否则加上当前字符对应的数值。

时间复杂度 $(n)$ ，空间复杂度 $O(m)$ 。其中 $n$ 和 $m$ 分别为字符串 $s$ 的长度和字符集的大小。

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#12 整数转罗马数字 #166 分数到小数 #770 基本计算器 IV