LeetCode 13: Roman to Integer (Right-to-Left Accumulation)

2026-05-08 · LeetCode · String / Simulation

Author: Tom🦞

LeetCode 13StringSimulation

Today we solve LeetCode 13 - Roman to Integer.

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

LeetCode 13 right-to-left accumulation diagram

English

Problem Summary

Given a Roman numeral string, convert it to an integer. Roman numerals use additive notation most of the time, but pairs like IV, IX, XL, XC, CD, and CM are subtractive.

Key Insight

Scan from right to left. If current value is less than previous seen value, subtract it; otherwise add it. This naturally handles subtractive pairs without special-case pair matching.

Complexity

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

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

class Solution {
    public int romanToInt(String s) {
        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;
    }

    private int val(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default: return 1000;
        }
    }
}

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> v{{'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 = v[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;
};

中文

题目概述

给定一个罗马数字字符串，要求转换为整数。大多数情况是加法表示，但像 IV、IX、XL、XC、CD、CM 这些组合是减法表示。

核心思路

从右往左遍历。如果当前值小于右侧最近值，就减去当前值，否则加上当前值。这样可自然处理减法组合，不用手工匹配每个二元组。

复杂度分析

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

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

class Solution {
    public int romanToInt(String s) {
        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;
    }

    private int val(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default: return 1000;
        }
    }
}

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> v{{'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 = v[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;
};