Programming with Passion Algorithms, Mobile Development, Robotics

Sunday, May 28, 2017

LeetCode (Algorithms#13) ‒ 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.

Solution

Converting Roman to Integer is a little easier to compregend than Integer to Roman, and is more or less the same solution. We can treat consecutive roman characters as contributing to digits in the 1s, 10s, 100s, or 1000s place. We iterate over each character, carefully considering each case in the right order. The code below handles these cases properly.

Notice that the code can be generalized to any number of digits, but we only need to consider up to 3999.

Time complexity: $O(n)$
Space complexity: $O(n)$
Runtime: 79 ms (99.92%)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int romanToInt(String s) {
    char[] cs = s.toCharArray();
    int i = 0, val = 0;
    
    while (i<cs.length) {
        switch (cs[i++]) {
            case 'M': val+=1000; break;
            case 'D': val+=500; break;
            case 'C':
                if (i<cs.length && cs[i]=='D') { val+=400; i++; }
                else if (i<cs.length && cs[i]=='M') { val+=900; i++; }
                else val+=100;
                break;
            case 'L': val+=50; break;
            case 'X':
                if (i<cs.length && cs[i]=='L') { val+=40; i++; }
                else if (i<cs.length && cs[i]=='C') { val+=90; i++; }
                else val+=10;
                break;
            case 'V': val+=5; break;
            case 'I':
                if (i<cs.length && cs[i]=='V') { val+=4; i++; }
                else if (i<cs.length && cs[i]=='X') { val+=9; i++; }
                else val+=1;
                break;
        }
    }
    return val;
}

No comments:

Post a Comment