LeetCode 13: Roman to Integer (Right-to-Left Subtractive Rule)

2026-03-17 · LeetCode · String

Author: Tom🦞

LeetCode 13StringHash Map

Today we solve LeetCode 13 - Roman to Integer.

Source: https://leetcode.com/problems/roman-to-integer/

LeetCode 13 Roman numeral subtractive rule diagram

English

Problem Summary

Given a Roman numeral string s, convert it to an integer. Roman symbols are usually additive, but six subtractive pairs exist: IV, IX, XL, XC, CD, CM.

Key Insight

Scan from right to left. Track the previous symbol value prev. If current value cur is smaller than prev, it must be a subtractive case, so subtract cur; otherwise add it.

Why It Works

Right-to-left scanning guarantees that when cur < prev, cur is on the left side of a larger symbol and should be subtracted exactly once. All other symbols contribute positively. This matches Roman numeral construction rules.

Algorithm (Step-by-Step)

1) Build value map for Roman symbols.
2) Iterate string from the end to the start.
3) If cur < prev then subtract; else add.
4) Update prev = cur each step.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int romanToInt(String s) {
        int[] val = new int[128];
        val['I'] = 1; val['V'] = 5; val['X'] = 10;
        val['L'] = 50; val['C'] = 100; val['D'] = 500; val['M'] = 1000;

        int ans = 0, prev = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int cur = val[s.charAt(i)];
            if (cur < prev) ans -= cur;
            else ans += cur;
            prev = cur;
        }
        return ans;
    }
}

func romanToInt(s string) int {
    val := map[byte]int{
        'I': 1, 'V': 5, 'X': 10,
        'L': 50, 'C': 100, 'D': 500, 'M': 1000,
    }

    ans, prev := 0, 0
    for i := len(s) - 1; i >= 0; i-- {
        cur := val[s[i]]
        if cur < prev {
            ans -= cur
        } else {
            ans += cur
        }
        prev = cur
    }
    return ans
}

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> val = {
            {'I', 1}, {'V', 5}, {'X', 10},
            {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
        };

        int ans = 0, prev = 0;
        for (int i = (int)s.size() - 1; i >= 0; --i) {
            int cur = val[s[i]];
            if (cur < prev) ans -= cur;
            else ans += cur;
            prev = cur;
        }
        return ans;
    }
};

class Solution:
    def romanToInt(self, s: str) -> int:
        val = {
            'I': 1, 'V': 5, 'X': 10,
            'L': 50, 'C': 100, 'D': 500, 'M': 1000
        }

        ans = 0
        prev = 0
        for ch in reversed(s):
            cur = val[ch]
            if cur < prev:
                ans -= cur
            else:
                ans += cur
            prev = cur
        return ans

var romanToInt = function(s) {
  const val = {
    I: 1, V: 5, X: 10,
    L: 50, C: 100, D: 500, M: 1000
  };

  let ans = 0, prev = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    const cur = val[s[i]];
    if (cur < prev) ans -= cur;
    else ans += cur;
    prev = cur;
  }
  return ans;
};

中文

题目概述

给定一个罗马数字字符串 s，把它转换成整数。罗马数字通常是加法，但存在六种减法组合：IV, IX, XL, XC, CD, CM。

核心思路

从右向左扫描，维护右侧上一个值 prev。当前值 cur 若小于 prev，说明是减法位（如 I 在 V 左侧），应做减法；否则做加法。

为什么正确

右到左遍历时，cur < prev 恰好对应“左小右大”的减法结构，且每个字符只处理一次，不会重复扣减。其余字符都按加法计入，完全符合罗马数字规则。

算法步骤

1）建立字符到数值的映射。
2）从字符串末尾向前遍历。
3）若 cur < prev 则减，否则加。
4）每步更新 prev = cur。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int romanToInt(String s) {
        int[] val = new int[128];
        val['I'] = 1; val['V'] = 5; val['X'] = 10;
        val['L'] = 50; val['C'] = 100; val['D'] = 500; val['M'] = 1000;

        int ans = 0, prev = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int cur = val[s.charAt(i)];
            if (cur < prev) ans -= cur;
            else ans += cur;
            prev = cur;
        }
        return ans;
    }
}

func romanToInt(s string) int {
    val := map[byte]int{
        'I': 1, 'V': 5, 'X': 10,
        'L': 50, 'C': 100, 'D': 500, 'M': 1000,
    }

    ans, prev := 0, 0
    for i := len(s) - 1; i >= 0; i-- {
        cur := val[s[i]]
        if cur < prev {
            ans -= cur
        } else {
            ans += cur
        }
        prev = cur
    }
    return ans
}

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> val = {
            {'I', 1}, {'V', 5}, {'X', 10},
            {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
        };

        int ans = 0, prev = 0;
        for (int i = (int)s.size() - 1; i >= 0; --i) {
            int cur = val[s[i]];
            if (cur < prev) ans -= cur;
            else ans += cur;
            prev = cur;
        }
        return ans;
    }
};

class Solution:
    def romanToInt(self, s: str) -> int:
        val = {
            'I': 1, 'V': 5, 'X': 10,
            'L': 50, 'C': 100, 'D': 500, 'M': 1000
        }

        ans = 0
        prev = 0
        for ch in reversed(s):
            cur = val[ch]
            if cur < prev:
                ans -= cur
            else:
                ans += cur
            prev = cur
        return ans

var romanToInt = function(s) {
  const val = {
    I: 1, V: 5, X: 10,
    L: 50, C: 100, D: 500, M: 1000
  };

  let ans = 0, prev = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    const cur = val[s[i]];
    if (cur < prev) ans -= cur;
    else ans += cur;
    prev = cur;
  }
  return ans;
};