Reference: 13. Roman to Integer / 12. Integer to Roman
Difficulty: Easy

My Post: Java Solutions of Roman to Integer & Integer to Roman (explanation, comments)

Conversion System

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
  • I can be placed before V (5) and X (10) to make IV (4) and IX (9).
  • X can be placed before L (50) and C (100) to make XL (40) and XC (90).
  • C can be placed before D (500) and M (1000) to make CD (400) and CM (900).

Roman to Integer

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: "III"
Output: 3

Input: "IV"
Output: 4

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

First, we need a function that receives a character and returns the corresponded value.

1
2
3
4
5
6
7
8
9
10
private int getVal(char ch) {
  if (ch == 'I') return 1;
  if (ch == 'V') return 5;
  if (ch == 'X') return 10;
  if (ch == 'L') return 50;
  if (ch == 'C') return 100;
  if (ch == 'D') return 500;
  if (ch == 'M') return 1000;
  throw new IllegalArgumentException("Unsupported Character");
}

The idea is very elegant. Each time we look ahead one element and compare the current element curr with the next element next.

  • curr < next: Combination, eg. IX.
  • curr >= next: Single Symbol, eg. III.

The way of handling symbols like IX is very clever. We first deduct the value of the first symbol and then add the value of the second symbol. For this example IX, we first deduct I(1) and then add X(5), which turns out to be 4.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int romanToInt(String s) {
  int n = s.length();
  int result = 0;
  
  if (n == 0) return result;
  
  for (int i = 0; i < n - 1; ++i) {
    int curr = getVal(s.charAt(i));
    int next = getVal(s.charAt(i + 1));
    if (curr < next) {
      result -= curr;
    } else {
      result += curr;
    }
  }
  return result + getVal(s.charAt(n - 1));
}

Actually, we can check the index before assigning a value to next. With this check, the code becomes more elegant and succinct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int romanToInt(String s) {
  int n = s.length();
  int result = 0;
  
  for (int i = 0; i < n; ++i) {
    int curr = getVal(s.charAt(i));
    int next = (i + 1 < n) ? getVal(s.charAt(i + 1)) : Integer.MIN_VALUE;
    if (curr < next) {
      result -= curr;
    } else {
      result += curr;
    }
  }
  return result;
}

Time: $O(N)$
Space: $O(1)$

Integer to Roman

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 3
Output: "III"

Input: 4
Output: "IV"

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

The idea is to check all possible bases from largest to smallest. For example, we should use M(1000) to reduce 1994 to 994, and then CM(900) and so on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public String intToRoman(int num) {
  int[] values = new int[] {
    1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
  };
  StringBuilder sb = new StringBuilder();
  for (int val : values) {
    if (val > num) continue;
    int numSymbol = num / val;
    while (numSymbol > 0) {
      sb.append(getSymbol(val));
      numSymbol -= 1;
    }
    num %= val;
  }
  return sb.toString();
}

private String getSymbol(int val) {
  if (val == 1)    return "I";
  if (val == 5)    return "V";
  if (val == 10)   return "X";
  if (val == 50)   return "L";
  if (val == 100)  return "C";
  if (val == 500)  return "D";
  if (val == 1000) return "M";
  if (val == 4)    return "IV";
  if (val == 9)    return "IX";
  if (val == 40)   return "XL";
  if (val == 90)   return "XC";
  if (val == 400)  return "CD";
  if (val == 900)  return "CM";
  throw new IllegalArgumentException("Unsupported Value");
}

Time: Depends on the value.
Space: $O(1)$