13.roman-to-integer.py

#
# @lc app=leetcode id=13 lang=python3
#
# [13] Roman to Integer
#
# Difficulty: Easy
# Frequency: 89.8%
# Tags: Hash Table, Math, String
# URL: https://leetcode.com/problems/roman-to-integer/
#
# --- Problem Description ---
#
# 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].
#

#
# --- Community Solutions ---
#
# https://leetcode.com/problems/roman-to-integer/solutions
#

# @lc code=start
# 这题其实在做什么：
# 把一串罗马字符还原成整数。大多数符号都是直接相加，唯一需要识别的
# 编码规则是“减法对”：小符号放在大符号左边时，表示要从大符号里扣掉它。
#
# 识别信号：
# - 输入是合法 Roman numeral，范围只有 1..3999。
# - 题目列出 IV、IX、XL、XC、CD、CM，说明核心不是字符串语法，
#   而是判断当前字符该加还是该减。
#
# =====================================================================
# 先看这题怎么做
# =====================================================================
#
# 直觉 / 画面感：罗马数字默认“从大到小，越往右越小”
# 正常情况符号从左到右递减（XVI = 10+5+1），直接相加。唯一例外：当一个小符号
# 出现在大符号左边（IV、CM），表示从右边那个大数里扣掉自己。
# 所以判断标准极简——只看当前字符和右邻居谁大：
#     s[i] <  s[i+1]  -> 当前在减法对左边 -> 减（贡献为负）
#     s[i] >= s[i+1]  -> 正常情况         -> 加（贡献为正）
# 为什么不“先识别两字符减法对再处理单字符”：那样要匹配 IV/IX/... 组合、跳两格，
# 分支多易漏；“只比相邻大小”把六种减法对统一成一条规则，代码短且不漏。
#
# 核心思路：
# 把每个字符转换成一个“带正负号的贡献值”，全部加起来就是答案。
# 如果 values[s[i]] < values[s[i+1]]，当前字符处在减法对左边，贡献为负；否则为正。
# 因为题目保证输入合法，比较相邻大小就足够捕捉所有合法减法对。
#
# 跑例：s = "MCMXCIV"
# - M 后面是 C，1000 >= 100，加 1000，ans = 1000
# - C 后面是 M，100 < 1000，减 100，ans = 900   <- CM 整体 = 900
# - M 后面是 X，加 1000，ans = 1900
# - X 后面是 C，减 10，ans = 1890               <- XC 整体 = 90
# - C 后面是 I，加 100，ans = 1990
# - I 后面是 V，减 1，ans = 1989                <- IV 整体 = 4
# - V 是最后一位，加 5，ans = 1994
#
# 关键不变量：
# 扫描到位置 i 后，ans 等于已扫描前缀按照罗马编码规则折算出的正确数值。
# 当前位只需要看右边一位：左小右大就减，否则就加，无需回看。
#
# 边界 / 易错点：
# - 最后一位没有右邻居，一定按正数加入；循环条件用 i+1 < len(s) 短路防越界。
# - 不要把 IV 当成 1 + 5；左边的小符号是“借位扣掉”的意思。
# - 最小反例 "IV"：忘了看右邻居会算成 1+5=6（错）；正确是 I 见更大的 V -> -1，
#   再 +5 = 4。两字符例子最能暴露“忘记减法规则”的 bug。
# - 如果题目不保证合法输入，就要显式校验减法对；本题不需要（见下方背景）。
#
# 落码步骤 / 伪代码骨架：
# 1. 建立 Roman 字符到数值的哈希表 values。
# 2. 初始化 ans = 0。
# 3. 从左到右扫描 s。
# 4. 如果 i+1 < len(s) 且 values[s[i]] < values[s[i+1]]，就减当前值；否则加当前值。
# 5. 返回 ans。
#
# 复杂度：
# 时间 O(n)，每个字符只看一次；空间 O(1)，映射表大小固定（7 项）。
#
# =====================================================================
# 补充背景（可跳过）：为什么“只比相邻大小”就够——靠输入合法性兜底
# =====================================================================
# 本轮答疑澄清的罗马数字合法性规则（理解用，代码不需处理，因输入保证合法）：
# - 减法对是“白名单”，只有六种：IV IX / XL XC / CD CM。
#   题面 line 33-37 明确列出这六种；“V/L/D 不能当减法左边”“同符号不连写四个”
#   等是从“只有这六种合法 + 输入保证合法”反推的推论，题面没有逐条写禁止句。
# - 每个减法对只含一个小符号：3 = III（不是 IIV），8 = VIII（不是 IIX）。
# - 不同档位可各用一次减法，但要从大到小排列：MCMXCIV 里 CM/XC/IV 各减一次。
# - 非法串（VIIV、IXII）不会出现；硬喂进算法会“垃圾进垃圾出”，但题目不会给。
# 关键洞察：正因为输入合法，“小符号在大符号左边”只会出现在那六种正规减法对里，
# 所以光比相邻大小就够，不必校验合法性。若允许非法输入，还需额外查白名单。
# 占位对照表（每档 0-9 同构）：3=CCC(百位) / 4=CD / 9=CM。
#
# =====================================================================
# 学完再记（可跳过）
# =====================================================================
# 一句模板：Roman 转整数 -> 当前字符“左小右大就减，否则加”。
# 记忆锚点：
# - 每个字符 = 带符号贡献值；符号由“和右邻居比大小”决定。
# - 末位无右邻居 -> 永远加；循环条件 i+1 < len(s) 短路防越界。
# - 同框架反过来就是 12 题（整数转 Roman），换成按面值贪心。
# 主动回忆检查：
# - 扫到位置 i 时 ans 代表什么？决定当前位加还是减需要看哪一格？
# - 改成从右往左扫，判断条件会变成什么（用 prev 怎么写）？
class Solution:
    def romanToInt(self, s: str) -> int:
        # Roman 字符到数值的固定映射（7 项，空间 O(1)）
        values = {"I": 1, "V": 5, "X": 10, "L": 50,
                  "C": 100, "D": 500, "M": 1000}

        ans = 0
        for i in range(len(s)):
            # 只看右邻居：当前值比右邻居小 -> 处在减法对左边（如 IV 的 I），贡献为负；
            # 否则正常相加。i + 1 < len(s) 短路保证末位（无右邻居）走 else 分支按正数加。
            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                ans -= values[s[i]]
            else:
                ans += values[s[i]]
        return ans

# @lc code=end