Convert Roman to Integer in Java Convert Roman to Integer in Java

Ashish Lahoti
Java
Page content

Problem: Given a Roman numeral, convert it to an Integer.

Source Code: RomanToInteger.java

Also read Convert Integer to Roman in Java

About Roman Numerals

A Quick look at roman numerals:-

I    = 1
II   = 2
III  = 3
IV   = 4
V    = 5
VI   = 6
VII  = 7
VIII = 8
IX   = 9
X    = 10
...
...
L    = 50
C    = 100
D    = 500
M    = 1000

Things to note about roman numerals:

  • When a symbol appears after a larger (or equal) symbol it is added
    Example: VI = V + I = 5 + 1 = 6
    Example: LXX = L + X + X = 50 + 10 + 10 = 70
  • But if the symbol appears before a larger symbol it is subtracted
    Example: IV = V − I = 5 − 1 = 4
    Example: IX = X − I = 10 − 1 = 9
  • If I appears just before V (5) and X (10), makes 4 and 9.
  • If X appears just before L (50) and C (100), makes 40 and 90.
  • If C appears just before D (500) and M (1000), makes 400 and 900.

Approach

Naive Approach

In this approach we’ll start checking each roman symbol from left to right keeping in mind the things about roman numerals as stated above.

// Approach 1
public static final int romanToInteger(String roman) {

	int number = 0;
	for (int i = 0; i < roman.length(); i++) {
		char c = roman.charAt(i);
		switch (c) {
		case 'I':
			number = (i != roman.length() - 1 && (roman.charAt(i + 1) == 'V' || roman.charAt(i + 1) == 'X'))
					? number - 1
					: number + 1;
			break;
		case 'V':
			number += 5;
			break;
		case 'X':
			number = (i != roman.length() - 1 && (roman.charAt(i + 1) == 'L' || roman.charAt(i + 1) == 'C'))
					? number - 10
					: number + 10;
			break;
		case 'L':
			number += 50;
			break;
		case 'C':
			number = (i != roman.length() - 1 && (roman.charAt(i + 1) == 'D' || roman.charAt(i + 1) == 'M'))
					? number - 100
					: number + 100;
			break;
		case 'D':
			number += 500;
			break;
		case 'M':
			number += 1000;
			break;
		}
	}

	return number;
}

Improvement using Map

We can further enhance our code to remove the switch statement in our code by saving roman numerals and their number values in Map.

// Approach 2
public static final int romanToInteger(String s) {

	Map<Character, Integer> values = new LinkedHashMap<>();
	values.put('I', 1);
	values.put('V', 5);
	values.put('X', 10);
	values.put('L', 50);
	values.put('C', 100);
	values.put('D', 500);
	values.put('M', 1000);

	int number = 0;
	for (int i = 0; i < s.length(); i++) {
		if (i+1 == s.length() || values.get(s.charAt(i)) >= values.get(s.charAt(i + 1))) {
			number += values.get(s.charAt(i));
		} else {
			number -= values.get(s.charAt(i));
		}
	}
	return number;
}

Dynamic (Recursive) Approach using Map

Though this is not an appropriate problem to apply dynamic programming. Still Let’s try our hands on how we can solve the same problem using recursive approach.

The changes we’ve done to make it recursive:-

  1. Brought the Map outside of method
  2. Created a private method getNumber() which gives us the number with respect to roman symbol.
  3. Added base condition index == s.length() in method to stop recursion
// Approach 3
private static Map<Character, Integer> map = new LinkedHashMap<>();
static {
	map.put('I', 1);
	map.put('V', 5);
	map.put('X', 10);
	map.put('L', 50);
	map.put('C', 100);
	map.put('D', 500);
	map.put('M', 1000);
}

public static final int romanToInteger(String s) {
	return romanToInteger(s, 0);
}

private static final int romanToInteger(String s, int index) {
	if(index == s.length()) {
		return 0;
	}
	return getNumber(s, index) + romanToInteger(s.substring(index+1, s.length()));
}

private static final int getNumber(String s, int index) {
	if(index+1 == s.length()) {
		return map.get(s.charAt(index));
	}
	
	if (map.get(s.charAt(index)) >= map.get(s.charAt(index+1))) {
		return map.get(s.charAt(index));
	} else {
		return -map.get(s.charAt(index));
	}		
}