Sponsored
Sponsored
The key idea is to traverse the given Roman numeral string from left to right. As we process each character, we compare it with the next one. If the current character has a smaller value than the next one, it means we are in a subtraction scenario (like IV = 4), so we subtract the value of the current character. Otherwise, we add its value.
Time Complexity: O(n), where n is the length of the string, because we make one pass through the string.
Space Complexity: O(1), constant space as the dictionary size does not depend on the input.
1#include <stdio.h>
2#include <string.h>
3
4int romanToInt(char* s) {
5 int values[256] = {};
6 values['I'] = 1;
7 values['V'] = 5;
8 values['X'] = 10;
9 values['L'] = 50;
10 values['C'] = 100;
11 values['D'] = 500;
12 values['M'] = 1000;
13
14 int total = 0;
15 int length = strlen(s);
16
17 for (int i = 0; i < length; i++) {
18 if (i + 1 < length && values[s[i]] < values[s[i + 1]]) {
19 total -= values[s[i]];
20 } else {
21 total += values[s[i]];
22 }
23 }
24
25 return total;
26}
27
28int main() {
29 char roman[] = "MCMXCIV";
30 printf("%d\n", romanToInt(roman)); // Output: 1994
31 return 0;
32}This C implementation starts by initializing a mapping from Roman symbols to their respective integer values using an array indexed by ASCII character codes. As we iterate through the Roman numeral string, we subtract or add the value based on the rule of subtraction.
In this approach, we traverse the string from right to left. We add the value of the current character to the total if it is greater or equal to its previous character; otherwise, we subtract it. Reverse traversal helps us intuitively handle the subtraction rule.
Time Complexity: O(n).
Space Complexity: O(1).
1import java
This Java version leverages a reverse iteration to decide early whether to add or subtract depending on last character value relevance.