LeetCode. 13. Roman to Integer

On this page

[Link] https://leetcode.com/problems/roman-to-integer/

Left-to-right scan

In a canonical Roman numeral, a symbol is subtracted only when it is immediately followed by a larger symbol. Thus IV is -1 + 5 = 4, while a symbol not in such a subtractive pair contributes its usual value. Comparing each symbol with its next symbol applies this rule directly. The loop invariant is that after each iteration, sum equals the signed contribution of every symbol processed so far: a symbol contributes negatively exactly when its next symbol is larger. Canonical notation guarantees that these local contributions express the numeral’s value. The final symbol has no successor and is always added.

The input is guaranteed to be a canonical Roman numeral representing a value from 1 through 3999, so no validation is needed.

Java

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            int current = valueOf(s.charAt(i));
            if (i + 1 < s.length() && current < valueOf(s.charAt(i + 1))) {
                sum -= current;
            } else {
                sum += current;
            }
        }
        return sum;
    }

    private int valueOf(char symbol) {
        switch (symbol) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default: return 1000; // M; the input is guaranteed to be valid.
        }
    }
}

Each symbol is examined a constant number of times, so the running time is $O(N)$ for a string of length $N$. The scan uses $O(1)$ extra space.