Tuesday, September 2, 2014

Leetcode: Roman to Integer

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Understand the problem:
The problem is just as opposite to the last problem. The crux is to get each string and convert it to digits, then it is straight-forward to convert digits into integer.

Solution:
The most challenge part of this problem is to split the string into valid roman numerals. The special case is for 4, 40, 400, and 9, 90, 900. Consider the following string:
MXXIV. which is 1024. However, it could be wrongly calculated as 1000 + 10 + 10 + 1 + 5 = 1006. To handle this situation, we could scan two characters at a time and check the special case.

Code (Java):
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        int i = 0;
        int num = 0;
        while (i < s.length()) {
            if (i <= s.length() - 2 && s.charAt(i) == 'I' && s.charAt(i + 1) == 'V') {
                num += 4;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'X' && s.charAt(i + 1) == 'L') {
                num += 40;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'C' && s.charAt(i + 1) == 'D') {
                num += 400;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'I' && s.charAt(i + 1) == 'X') {
                num += 9;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'X' && s.charAt(i + 1) == 'C') {
                num += 90;
                i += 2;
            } else if (i <= s.length() - 2 && s.charAt(i) == 'C' && s.charAt(i + 1) == 'M') {
                num += 900;
                i += 2;
            } else {
                num += toInteger(s.charAt(i));
                i++;
            }
        }
        return num;
    }
    
    private int toInteger(char roman) {
        int num = 0;
        switch(roman) {
            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;
        }
        return num;
    }
}

A better Solution:
Again, the solution above is self-explained, but look redundant. For the case where 4, 40, 400, 9, 90, 900, we can see that if the first character is less than second, e.g. 4 is IV, we know that it must be in either the case above. Else, VI, we know that it is 5 + 1 = 6. 
Consequently, we can use this property to shorten the code above.

Code (Java):
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) return 0;
        
        // create a hash table to store the dictorary
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        hashMap.put('I', 1);
        hashMap.put('V', 5);
        hashMap.put('X', 10);
        hashMap.put('L', 50);
        hashMap.put('C', 100);
        hashMap.put('D', 500);
        hashMap.put('M', 1000);
        
        int num = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (i <= s.length() - 2 && 
                hashMap.get(s.charAt(i)) < hashMap.get(s.charAt(i + 1))) {
                num -= hashMap.get(s.charAt(i));
            } else {
                num += hashMap.get(s.charAt(i));
            }
        }
        return num;
    }
}

Summary:
The problem is not hard. However, note that how 4, 40, 400, 9, 90, 900 are represented in the Roman numerals. 

No comments:

Post a Comment