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.
1import java.util.HashMap;
2import java.util.Map;
3
4public class RomanToInt {
5 public int romanToInt(String s) {
6 Map<Character, Integer> values = new HashMap<>();
7 values.put('I', 1);
8 values.put('V', 5);
9 values.put('X', 10);
10 values.put('L', 50);
11 values.put('C', 100);
12 values.put('D', 500);
13 values.put('M', 1000);
14
15 int total = 0;
16 for (int i = 0; i < s.length(); i++) {
17 if (i + 1 < s.length() && values.get(s.charAt(i)) < values.get(s.charAt(i + 1))) {
18 total -= values.get(s.charAt(i));
19 } else {
20 total += values.get(s.charAt(i));
21 }
22 }
23
24 return total;
25 }
26
27 public static void main(String[] args) {
28 RomanToInt converter = new RomanToInt();
29 System.out.println(converter.romanToInt("MCMXCIV")); // Output: 1994
30 }
31}This Java solution uses a HashMap to store Roman numeral values. The traversal logic is similar to the C/C++ methods, using subtraction for certain numeral pairs.
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).
1using System;
using System.Collections.Generic;
class RomanToIntReverse {
public int RomanToIntFromRight(string s) {
Dictionary<char, int> values = new Dictionary<char, int> {
{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
{'C', 100}, {'D', 500}, {'M', 1000}
};
int total = 0;
int last_value = 0;
for (int i = s.Length - 1; i >= 0; i--) {
int current_value = values[s[i]];
if (current_value < last_value) {
total -= current_value;
} else {
total += current_value;
}
last_value = current_value;
}
return total;
}
static void Main(string[] args) {
RomanToIntReverse converter = new RomanToIntReverse();
Console.WriteLine(converter.RomanToIntFromRight("LVIII")); // Output: 58
}
}This C# code uses a reverse loop over the input, enabling each Roman numeral to be considered in relation to its successor, allowing clear decision-making for increments or decrements.