LeetCode Integer to Roman: Find the Mapping

Overview

The key to solve this LeetCode Integer to Roman problem is to figure the corresponding mapping from the digits to Roman numbers.

LeetCode Integer to Roman Problem

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solutions: Find the Mapping

The key is to figure the corresponding mapping from the digits to Roman numbers. The following is the mapping:

string mapping[4][10] = {
{“”, “M”, “MM”, “MMM”, “”, “”, “”, “”, “”, “”}, //0 – 3000
{“”, “C”, “CC”, “CCC”, “CD”, “D”, “DC”, “DCC”, “DCCC”, “CM”}, //100 – 900
{“”, “X”, “XX”, “XXX”, “XL”, “L”, “LX”, “LXX”, “LXXX”, “XC”}, //10 – 90
{“”, “I”, “II”, “III”, “IV”, “V”, “VI”, “VII”, “VIII”, “IX”} //0 – 9
};

So we parse the given number into digits, like 1738, then we get 1, 7, 3, 8. 1 corresponds to the first row in the mapping array (M), and 7 corresponds to the second row (DCC), and 3 corresponds to the third row (XXX), finally, 8 corresponds to the 4-th row (VIII). We then get MDCCXXXVIII. This yields the following compact and quite simple code:

string intToRoman(int num) {
    string mapping[4][10] = {
        {"", "M", "MM", "MMM", "", "", "", "", "", ""}, //0 - 3000 
        {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}, //100 - 900
        {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}, //10 - 90
        {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"} //0 - 9 
    };
    string ret("");
    for (int i = 1000, j = 0; i > 0; num %= i, i /= 10, ++j) {
        ret += mapping[j][num / i];
    }
    return ret;
}

Summary

The key to solve this LeetCode Integer to Roman problem is to figure the corresponding mapping from the digits to Roman numbers.

Written on May 9, 2013