Leetcode–Roman to Integer

The Problem:

Given a roman numeral, convert it to an integer.

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

Notes:

  1. First need to know about Roman numbers: I – 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000. For special representation of 4 and 9, it’s simpler to just hard code the rules and insert to the above list. Then only need to check if number > (1000,900,…), if so append a symbol accordingly.
  2. Be careful about checking the range in the match function.

Java Solution

public class Solution {
    public int romanToInt(String s) {
        //I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000.
        //only need to check if greater than 10-9-5-4-1
        String[] sym = {"M","CM", "D","CD", "C", "XC", "L", "XL", "X", "IX", "V","IV" ,"I"};
        int[] scale = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int result = 0;
        int i = 0; 
        int j = 0;
        while( i < s.length()){
            if(match(s, i, sym[j])){
                result += scale[j];
                i+= sym[j].length();
            }
            else{
                j++;
            }
        }
        return result;
    }    
    private boolean match(String a, int id, String b){
        int l = b.length();
        if(a.length()-id < l)return false;
        return b.equals(a.substring(id,id+l));
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s