Why it works
- With only the symbols below a value, a correct numeral stays under that value: below CM = 900 the most is DCCCXCIX = 899. So when a value fits, the numeral has to take it now; the smaller ones cannot make it up.
- The pairs CM, CD, XC, XL, IX and IV are in the table as values of their own. Thanks to them greed never needs four of a kind: 94 becomes XC + IV, not LXXXX + IIII.
- num only shrinks, and the table is walked once from the top, so the symbols come out from the biggest down, as Roman numerals require.
Complexity
Time O(1): the table has 13 values, and no symbol is written more than three times in a row, so at most 15 symbols come out. Memory O(1) besides the answer.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗