Roman to Integer

def romanToInt(s):
    val = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
           'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and val[s[i]] < val[s[i+1]]:
            total -= val[s[i]]
        else:
            total += val[s[i]]
    return total

Roman to Integer. The Romans wrote numbers with seven letters: I is one, V is five, X ten, L fifty, C a hundred, D five hundred, and M a thousand. Turn a numeral into a number.

Usually, just add them up. I I I is three, and L V I I I is fifty, plus five, plus three: fifty-eight. But a smaller letter before a bigger one is subtracted: I V is four, and I X is nine.

The naive way keeps a table of the six subtracting pairs: I V, I X, X L, X C, C D and C M. It checks for a pair before each single letter. It works, but that's a lot of special cases.

Better: one rule covers them all. Compare each letter with the one after it. If it's smaller than its neighbour, subtract it. Otherwise, add it.

In code, a lookup table gives each letter's value. Walk left to right: if the next value is bigger, subtract this one, else add it. Then return the total.

Try M C M X C I V. M, then a smaller C: add a thousand. C, then a bigger M: subtract a hundred, nine hundred. M: add, nineteen hundred. X before C: subtract ten, eighteen ninety. C: add, nineteen ninety. I before V: subtract one, nineteen eighty-nine. And V is last: add five. Nineteen ninety-four.

Each letter is looked at once: order n time. And the table has seven entries, with one running total: order one space.

Look it up, peek ahead, add or subtract. That's Roman to Integer.