Saturday, May 23, 2015

Roman To Integer

Problem Statement

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space

Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/roman-to-integer/
Solution

public int RomanToInt(string s)
{
    // Input validation
    if (string.IsNullOrEmpty(s))
        return 0;

    // 4:IV, 9:IX, 40:XL, 90:XC, 400:CD, 900:CM,
    // 1:I, 10:X, 100:C, 1000:M
    int output = 0;
    // Prev is previous character in the input string
    char pre = ' ';

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == 'M' && pre != 'C') { output += 1000; }
        if (s[i] == 'C' && pre != 'X') { output += 100; }
        if (s[i] == 'X' && pre != 'I') { output += 10; }

        if (s[i] == 'M' && pre == 'C') { output += 800; }
        if (s[i] == 'C' && pre == 'X') { output += 80; }
        if (s[i] == 'X' && pre == 'I') { output += 8; }

        if (s[i] == 'I') { output += 1; }

        if (s[i] == 'V' && pre != 'I') { output += 5; }
        if (s[i] == 'L' && pre != 'X') { output += 50; }
        if (s[i] == 'D' && pre != 'C') { output += 500; }

        if (s[i] == 'V' && pre == 'I') { output += 3; }
        if (s[i] == 'L' && pre == 'X') { output += 30; }
        if (s[i] == 'D' && pre == 'C') { output += 300; }

        pre = s[i];

    }

    // Return output
    return output;
}

No comments:

Post a Comment