LeetCode Roman to Integer: Find the Pattern

Overview

The key to solve this LeetCode Roman to Integer problem is to find or summarize the pattern about the conversion rules between roman number and integers.

LeetCode Roman to Integer Problem

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Solutions: How to Find the Pattern

This is easy. Scan through the string from left to right, every time we need scan a consecutive substring until we encounter a different character. For example, MMCD we need MM, C, D. To deal with the current substring we get, we first get the decimal value of the substring by multiplying length(substring) with the decimal value of that character in that subtring (in MM, we get 2 * 1000). Then we check the next character, if it is a larger one than the character in the substring, then we subtract the decimal value of the substring from the final result. Otherwise, we add this value into the final result. This is directly a simulation of the rules of the Roman numbers. The following C++ source code is accepted by LeetCode OJ to pass this Roman To Integer problem:

int val(char c) {
    switch (c) {
        case 'I':
            return 1;
        case 'V':
            return 5;
        case 'X':
            return 10;
        case 'L':
            return 50;
        case 'C':
            return 100;
        case 'D':
            return 500;
        case 'M':
            return 1000;
        default:
            return -1;
    }
}
int romanToInt(string s) {
    int n = s.size();
    if (n <= 0) return 0;
    if (1 == n) return val(s[0]);
    int ret = 0, cnt = 1, i = 1;

    while (i < n) {
        while (i < n && s[i] == s[i - 1]) {
            ++i, ++cnt;
        }
        if (val(s[i]) > val(s[i - 1]))
            ret -= val(s[i - 1]) * cnt;
        else
            ret += val(s[i - 1]) * cnt;
        if (i >= n) return ret;

        cnt = 1, ++i;
        if (i >= n) ret += val(s[i - 1]) * cnt;
    }
    return ret;
}

Summary

The key to solve this LeetCode Roman to Integer problem is to find or summarize the pattern about the conversion rules between roman number and integers.

Written on May 9, 2013