Thursday, April 17, 2014

[LeetCode] Roman to Interger

Problem Statement (link):
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Analysis:
There isn't so much to say about this problem. Just adding the number together. When the number current char represents is smaller than that of the next char, to calculate the number that these two chars represent, you need to subtract the number that current char represents from that of the next char. e.g., XXIX, the first two X represent 10+10, the next IX represent 10-1, thus the result is 10+10+(10-1)=29.

A comprehensive description of the rules of Roman Numeral is here. Unfortunately, the link is Chinese.

Code:
class Solution {
public:
    int romanToInt(string s) {
        if (s.empty()) return 0;
        int out=0, i=0;
        while (i<s.size()) {
            if (i+1<s.size() && helper(s[i])<helper(s[i+1])) { // the next char exists and it's greater than curr
                out+=helper(s[i+1])-helper(s[i]);
                i++;
            }
            else
                out+=helper(s[i]);
            i++;
        }
        return out;
    }

    int helper(char c) {
        int num=0;
        switch(c) {
            case 'I':
                num=1;
                break;
            case 'V':
                num=5;
                break;
            case 'X':
                num=10;
                break;
            case 'L':
                num=50;
                break;
            case 'C':
                num=100;
                break;
            case 'D':
                num=500;
                break;
            case 'M':
                num=1000;
                break;
            default:
                num=0;
                break;
        }
        return num;
    }
};

No comments:

Post a Comment