💬 Discord
Sign In
NeetCode #913LC-13EasyMath & GeometryNC 250
← Back to All Problems

#913 · #13 · Roman to Integer(罗马数字转整数)

📌 Problem Statement & Constraints

Given a valid Roman numeral string s, convert it to an integer. Roman numerals use the symbols I, V, X, L, C, D, M and are written largest-to-smallest except for six subtractive combinations (IV, IX, XL, XC, CD, CM). Constraints: 1 <= s.length <= 15, s consists only of those seven symbols and represents a value in [1, 3999].

💡 Core Algorithmic Approaches

  1. Map each of the seven symbols to its integer value.
  2. Scan left to right. If the current symbol's value is smaller than the next symbol's value, it belongs to a subtractive pair, so subtract it; otherwise add it.
  3. This single sign rule reproduces all six subtractive forms without any special-casing.
  4. Summing the signed values gives the integer directly in one pass.

💻 Benchmark Python3 Implementation

class Solution:
    def romanToInt(self, s: str) -> int:
        vals = {"I": 1, "V": 5, "X": 10, "L": 50,
                "C": 100, "D": 500, "M": 1000}
        total = 0
        for i, ch in enumerate(s):
            v = vals[ch]
            if i + 1 < len(s) and v < vals[s[i + 1]]:
                total -= v            # part of a subtractive pair
            else:
                total += v
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single left-to-right pass.
💾 Space Complexity
O(1): a fixed-size lookup table.

⚠️ Interview Pitfalls & Follow-ups

  • Indexing s[i + 1] without a bounds check: the last character has no successor, so the guard i + 1 < len(s) is required.
  • Hardcoding each subtractive pair: enumerating IV, IX, and the rest is error-prone; the sign rule is uniform.
  • Adding both symbols of a pair and then correcting: the sign rule handles IV as -1 + 5 with no lookahead bookkeeping.
  • Assuming the input may be invalid: the problem guarantees a valid numeral, so no validation is needed.