The Roman to Integer problem on LeetCode is a common coding challenge that asks you to convert a Roman numeral represented as a string into an integer.

For example, 2 is written as `II`

in Roman numeral, just two ones added together. 12 is written as `XII`

, which is simply `X + II`

. The number 27 is written as `XXVII`

, which is `XX + V + II`

.

Roman numerals are a numeral system that originated in ancient Rome and were used throughout the Roman Empire. They are still used today in some contexts, such as numbering the chapters or sections of books, indicating the copyright dates of books, and for decorative purposes. Roman numerals use a combination of letters from the Latin alphabet to represent numbers.

Roman | Integer |
---|---|

I | 1 |

V | 5 |

X | 10 |

L | 50 |

C | 100 |

D | 500 |

M | 1000 |

Here’s how Roman numerals work:

- Roman numerals are written from left to right.
- When a smaller number appears before a larger number, you subtract the smaller number. For example,
`IV`

represents 4 = 5 - 1, and`IX`

represents 9 = 10 - 1. - When a smaller number appears after a larger number, you add the smaller number. For example,
`VII`

represents 7 = 5 + 2, and`XIV`

represents 14 = 10 + 1 + 3. - You can repeat a symbol up to three times in a row to add its value. For example,
`III`

represents 3 = 1 + 1 + 1. - You can’t repeat the same subtractive pair more than once. For example, 4 is represented as
`IV`

, not`IIII`

, and 9 is represented as`IX`

, not`VIIII`

.

To convert a Roman numeral string into an integer, you need to add up the values of the individual symbols while considering a special rule: If a smaller symbol appears before a larger symbol, you should subtract the value of the smaller symbol.

Here’s solution in C++:

```
#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;
int romanToInt(string s) {
unordered_map<char, int> romanNumerals = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int result = 0;
int prevValue = 0;
for (int i = s.length() - 1; i >= 0; i--) {
int currentValue = romanNumerals[s[i]];
if (currentValue < prevValue) {
result -= currentValue;
} else {
result += currentValue;
}
prevValue = currentValue;
}
return result;
}
int main() {
// Test cases with assertions
assert(romanToInt("III") == 3);
assert(romanToInt("IV") == 4);
assert(romanToInt("IX") == 9);
assert(romanToInt("LVIII") == 58);
assert(romanToInt("MCMXCIV") == 1994);
cout << "All test cases passed!" << endl;
return 0;
}
```

The solution uses a mapping of Roman numeral characters to their integer values and iterates through the input string, adjusting the result based on the current and next characters as per the rules. It covers the basic symbols and the subtractive combinations as required to handle valid Roman numerals.

Polynomial Rolling HashJun 06, 2024

Big-O NotationFeb 06, 2024

Rabin–Karp String SearchingSep 10, 2021

Dynamic Programming (DP)Jan 16, 2022

Bloom FilterFeb 02, 2022

Competitive Programming TopicsFeb 02, 2022

Data Structures Used in Competitive ProgrammingFeb 04, 2022