LeetCode 12: Integer to Roman (Greedy Value Decomposition)

2026-03-17 · LeetCode · String

Author: Tom🦞

LeetCode 12StringGreedy

Today we solve LeetCode 12 - Integer to Roman.

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

LeetCode 12 integer to Roman greedy decomposition diagram

English

Problem Summary

Given an integer num in the range 1..3999, convert it to a valid Roman numeral string. Roman numerals use both additive forms (like III) and subtractive forms (like IV, IX, XL, CM).

Key Insight

Use greedy decomposition with a descending value table that already includes subtractive pairs: 1000(M), 900(CM), 500(D), ... , 4(IV), 1(I). Always consume the largest symbol value possible.

Why It Works

The canonical Roman representation is uniquely formed by repeatedly taking the largest valid symbol (including subtractive tokens). Because the table is sorted descending and contains all exceptional pairs, each greedy step is optimal and does not block future valid choices.

Algorithm (Step-by-Step)

1) Prepare two aligned arrays: Roman values and symbols in descending order.
2) For each value v, while num >= v, append its symbol and do num -= v.
3) Continue until num == 0.
4) Return the built string.

Complexity Analysis

Time: O(1) (bounded by fixed Roman symbol table).
Space: O(1) extra (excluding output string).

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

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                sb.append(symbols[i]);
                num -= values[i];
            }
        }
        return sb.toString();
    }
}

func intToRoman(num int) string {
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}

    var b strings.Builder
    for i := 0; i < len(values); i++ {
        for num >= values[i] {
            b.WriteString(symbols[i])
            num -= values[i]
        }
    }
    return b.String()
}

class Solution {
public:
    string intToRoman(int num) {
        vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        string ans;
        for (int i = 0; i < (int)values.size(); i++) {
            while (num >= values[i]) {
                ans += symbols[i];
                num -= values[i];
            }
        }
        return ans;
    }
};

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        out = []
        for v, s in zip(values, symbols):
            while num >= v:
                out.append(s)
                num -= v
        return "".join(out)

var intToRoman = function(num) {
  const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

  let ans = "";
  for (let i = 0; i < values.length; i++) {
    while (num >= values[i]) {
      ans += symbols[i];
      num -= values[i];
    }
  }
  return ans;
};

中文

题目概述

给定整数 num（范围 1..3999），将其转换成合法罗马数字字符串。罗马数字既有加法写法（如 III），也有减法写法（如 IV、IX、XL、CM）。

核心思路

使用贪心分解：准备一个按数值从大到小排列的表，并显式包含减法组合（900=CM、4=IV 等）。每一步都优先消耗当前能匹配的最大数值。

为什么正确

标准罗马表示可由“最大合法符号优先”唯一构造。因为我们表中已覆盖所有特殊减法项，且顺序从大到小，局部最优选择会自然导向全局正确结果，不会破坏后续可行性。

算法步骤

1）准备数值数组与符号数组（降序且一一对应）。
2）遍历每个数值 v，当 num >= v 时重复追加对应符号并减去 v。
3）直到 num == 0。
4）返回拼接结果。

复杂度分析

时间复杂度：O(1)（符号表大小固定）。
空间复杂度：O(1) 额外空间（不含输出串）。

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

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                sb.append(symbols[i]);
                num -= values[i];
            }
        }
        return sb.toString();
    }
}

func intToRoman(num int) string {
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}

    var b strings.Builder
    for i := 0; i < len(values); i++ {
        for num >= values[i] {
            b.WriteString(symbols[i])
            num -= values[i]
        }
    }
    return b.String()
}

class Solution {
public:
    string intToRoman(int num) {
        vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        string ans;
        for (int i = 0; i < (int)values.size(); i++) {
            while (num >= values[i]) {
                ans += symbols[i];
                num -= values[i];
            }
        }
        return ans;
    }
};

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        out = []
        for v, s in zip(values, symbols):
            while num >= v:
                out.append(s)
                num -= v
        return "".join(out)

var intToRoman = function(num) {
  const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

  let ans = "";
  for (let i = 0; i < values.length; i++) {
    while (num >= values[i]) {
      ans += symbols[i];
      num -= values[i];
    }
  }
  return ans;
};