Convert Roman Numerals to Arabic


  • 1
    H

    Given a string representing Roman numerals, convert to Arabic.

    E.g., an input 'CXVI' is equivalent to 116.


  • 0
    I

    Same as Roman to Integer. Was this phone or onsite?


  • 1

    @hknajjar Did the interviewer define the roman number range?


  • 1
    T

    If you define each letter to have a value in a map, then you can iterate through the string in reverse and add or subtract. The prefix can only have the previous letter once, but the letter can suffix up to three times. But this does not matter because you just add them up. You do need some way to keep track of the last value so you know whether or not to add or subtract, which is what I used a list for in a stack style down below. Did I miss anything?

    map = dict(
        I=1,
        V=5,
        X=10,
        L=50,
        C=100,
        D=500,
        M=1000,
    )
    
    value = 0
    stack = []
    
    s = 'MMXIV'  # 2014
    
    for c in s[::-1]:
        a = map[c]
        if stack and stack[-1] > a:
            stack.pop()
            value -= a
        else:
            stack.append(a)
            value += a
    
    print(value)
    

  • 0
    V

    public int covertToDec (String string) {
    char [] ch = string.toCharArray();
    int res = 0 , curr_val = 0;
    char prev = ch[0], curr;
    if (ch[0] == ' ') {
    return Integer.MIN_VALUE;
    }
    for (int i=0; i<ch.length; i++) {
    curr = ch[i];
    curr_val = map.get(curr);
    if (prev!=' ' && curr_val > map.get(prev)) {
    res+= curr_val - (map.get(prev))*2;
    } else {
    res+=curr_val;
    }
    prev = curr;
    }
    return res;
    }

    This is the map :
    map.put('I',1);
    map.put('V',5);
    map.put('X',10);
    map.put('L',50);
    map.put('C',100);
    map.put('D',500);

    • list itemmap.put('M',1000);


  • 0
    N

    @tatsh Good solution. You might simplify it by making a small tweak.
    Move from Greatest to Least character (i.e. Left to Right of the string)
    For each character, check if it is smaller than the next character to its right. If yes, then subtract the smaller character's value from the result, else add the value to the result.

    int res = 0
    for c in range(0, len(s)-1):
          if map[c] < map[c+1]:
                res -= map[c]
          else:
                res += map[c]
    
    #add value of last character
    res += map[len(s)-1]    
             
    return res    
    

  • 0
    T

    @nrl Glad to see an improvement. I presume map = [1, 5, 10, ...] (could use a better name?) right?


  • 0
    N

    @tatsh Haha, maybe. But I always use 'hm' for HashMap in Java, so maybe I am not the right person to comment on that :-)


  • 1
    int convertFromRomanToArabic(String roman) {
    		int result = 0;
    
    		Map<Character, Integer> map = new HashMap<>();
    		map.put('M', 1000);
    		map.put('D', 500);
    		map.put('C', 100);
    		map.put('L', 50);
    		map.put('X', 10);
    		map.put('V', 5);
    		map.put('I', 1);
    
    		int i = roman.length() - 1;
    		while (i >= 0) {
    			if (i + 1 < roman.length() && map.get(roman.charAt(i + 1)) > map.get(roman.charAt(i)))
    				result -= map.get(roman.charAt(i));
    			else
    				result += map.get(roman.charAt(i));
    			i--;
    		}
    		return result;
    	}
    

  • 1
    S
    int nums[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
    String symbols[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
    
    public int romanToInt(String s) {
        int num = 0;
        while (s.length() > 0) {
            for (int i = nums.length - 1; i >= 0; i--) {
                if (s.startsWith(symbols[i])) {
                    num += nums[i];
                    s = s.substring(symbols[i].length());
                    break;
                }
            }
        }
    
        return num;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.