PU Roman to Integer

Jan 01, 1970

Given a roman numeral, convert it to an integer.

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

C Solution 1:

int romanToInt(char* s) {
    int res = 0;
    char *p;

    for (p = s; *p == 'M'; p++);
    res += (p - s) * 1000;

    for (s = p; *p == 'C' || *p == 'D' || *p == 'M'; p++);
    if (p != s) {
        if (*(p - 1) == 'M') res += 900;
        else if (*(p - 1) == 'D') res += 500 - (p - s - 1) * 100;
        else {
            if (*s == 'C') res += (p - s) * 100;
            else res += 500 + (p - s - 1) * 100;
        }
    }

    for (s = p; *p == 'X' || *p == 'L' || *p == 'C'; p++);
    if (p != s) {
        if (*(p - 1) == 'C') res += 90;
        else if (*(p - 1) == 'L') res += 50 - (p - s - 1) * 10;
        else {
            if (*s == 'X') res += (p - s) * 10;
            else res += 50 + (p - s - 1) * 10;
        }
    }

    for (s = p; *p == 'I' || *p == 'V' || *p == 'X'; p++);
    if (p != s) {
        if (*(p - 1) == 'X') res += 9;
        else if (*(p - 1) == 'V') res += 5 - (p - s - 1);
        else {
            if (*s == 'I') res += p - s;
            else res += 5 + (p - s - 1);
        }
    }
    return res;

}

C Solution 2:

int romanToInt(char* s) {
    int flag[256];
    flag[0] = 0;
    flag['I'] = 1;
    flag['V'] = 5;
    flag['X'] = 10;
    flag['L'] = 50;
    flag['C'] = 100;
    flag['D'] = 500;
    flag['M'] = 1000;

    int res = 0;
    for (; *s; s++) {
        if (flag[*s] < flag[*(s + 1)]) {
            res -= flag[*s];
        }
        else {
            res += flag[*s];
        }
    }
    return res;
}

Summary:

  1. The last solution clearly demonstrate the logic. For the last character, it definitely is a plus, so set flag[0] = 0 first to make flag[*s] > flag[0].
  2. The first: 29ms, 34.21%. The Second: 25ms, 66.67%.
  3. To solve this problem, Abstracting the logic behind is the point.

LeetCode: 13. Roman to Integer