Roman to Integer

NeetCode: Roman to Integer · LeetCode: 13. Roman to Integer · Difficulty: Easy

Roman numerals use the symbols I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Symbols are normally written largest to smallest and added, but six subtractive pairs exist: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. Given a valid Roman numeral s (value 1 to 3999), return its integer value.

Example

Text

Input:  s = "III"        Output: 3
Input:  s = "LVIII"      Output: 58
Input:  s = "MCMXCIV"    Output: 1994

Brute force: greedy token table

List all 13 tokens (the 7 symbols plus the 6 subtractive pairs), longest value first. At every position, try the tokens in that order; the two-character tokens come before the single character they start with, so they win. s.startsWith(token, pos) tests whether token occurs at index pos. This needs a larger table and up to 13 comparisons at every position.

Java

class Solution {
    public int romanToInt(String s) {
        String[] tokens = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int pos = 0;
        int total = 0;
        while (pos < s.length()) {
            for (int t = 0; t < tokens.length; t++) {
                if (s.startsWith(tokens[t], pos)) {
                    total += values[t];
                    pos += tokens[t].length();
                    break;
                }
            }
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.romanToInt("III"));
        System.out.println(s.romanToInt("LVIII"));
        System.out.println(s.romanToInt("MCMXCIV"));
    }
}

Output

3
58
1994

Time: O(n) (13 tokens per position is a constant). Space: O(1).

Optimal: right-to-left with the subtractive rule

A symbol is subtracted exactly when a larger symbol follows it (I before V, C before M, ...). So scan from the right, remembering the value of the symbol just to the right. If the current value is smaller than that, subtract it, otherwise add it. Only the seven-symbol table and one pass are needed.

For MCMXCIV from the right: V +5, I (1 < 5) -1, C +100, X (10 < 100) -10, M +1000, C (100 < 1000) -100, M +1000, total 1994.

Java

class Solution {
    private int value(char c) {
        return switch (c) {
            case 'I' -> 1;
            case 'V' -> 5;
            case 'X' -> 10;
            case 'L' -> 50;
            case 'C' -> 100;
            case 'D' -> 500;
            case 'M' -> 1000;
            default -> 0;
        };
    }

    public int romanToInt(String s) {
        int total = 0;
        int prev = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int v = value(s.charAt(i));
            if (v < prev) {
                total -= v;
            } else {
                total += v;
            }
            prev = v;
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.romanToInt("III"));
        System.out.println(s.romanToInt("LVIII"));
        System.out.println(s.romanToInt("MCMXCIV"));
    }
}

Output

3
58
1994

Time: O(n). Space: O(1).

Both are linear. Working right to left needs no look-ahead, so there is no index to keep in bounds.