LeetCode: Roman to Integer in Java

Question

I tried solve this easy leetcode challenge in java. Challenge link

Here is my solution

class Solution {
  public int romanToInt(String s) {
    Map<String, Integer> data 
        = new HashMap<String, Integer>() {
        {
            put("I", 1);
            put("V", 5);
            put("X", 10);
            put("L", 50);
            put("C", 100);
            put("D", 500);
            put("M", 1000);
            put("IV", 4);
            put("IX", 9);
            put("XL", 40);
            put("XC", 90);
            put("CD", 400);
            put("CM", 900);
        }
    };
    String[] edge = {"IV", "IX", "XL", "XC", "CD", "CM"};    
      int sum = 0;  
      for (String val : edge) { 
          if(s.isBlank()) {
              break;
          } else if(s.contains(val)) {
             sum += data.get(val);
             int index = s.indexOf(val); 
             s = s.substring(0, index) + s.substring(index + 2);
          }
      }
      s = s.trim();
      for (char c: s.toCharArray()) {
          sum += data.get("" + c);
      }
      return sum;  
      }
}

I am learning to compute the complexity:
Here is my interpretation
Looks like it is O(6) constant ~ O(1) * O(len(string)) ~ O(n) => O(n) Correct me if it is not O(n)

Any suggestions on my approach to problem and code where I can reduce time and space complexity.

Answer 1

Your variable names are bad, s, data, all of these could be better, input, romanNumerals and so on.

Your formatting is a little bit off, consider using an autoformatter.

Also your method will spectacularly fail when handed invalid input.

---

put("I", 1);

Be aware of Autoboxing.

---

for (String val : edge) { 
    if(s.isBlank()) {

Have the if outside the loop, so that you don't even need to start the loop just to bail out immediately.

---

sum += data.get("" + c);

I'm absolutely not a friend of such casts. Most of the time, they mask what you actually wanted and depend on implementation details, especially with numbers.

---

Otherwise it seems to work. What you could do is split the initial Map into two, romanNumerals and compoundRomanNumerals, that would simplify the overall logic and would remove the duplication you have with the edge array.

If you can help it, try to avoid string operations, they will always consume a lot of memory, for example:

String c = a + b;

Will result in:

1. Allocate c with enough memory to hold a and b
2. Copy a into c
3. Copy b into c

So if a and/or b is large, and I mean large, your memory usage will spike.

What you could do instead, is to copy the String into a StringBuilder, as that one will internally work on an array and will not create immutable instances with every change.

And you should handle error cases, null as input, Hello World! as input, such stuff. Would be a great exercise for writing unittests.

Answer 2

In this case, I think that you can simplify the algorithm quite a bit. The compound numbers are simply the left value subtracted from the right value. This can easily be calculated on the fly. This cuts down the HashMap to only 7 entries and eliminates the edgevariable. Basically it could look like this:

final Map<Character,Integer> values = Map.of(
    'I',1,
    'V',5,
    'X',10,
    'L',50,
    'C',100,
    'D',500,
    'M',1000
);

public int romanToInt(String input){       
    int retVal = 0;
    int limit = input.length();
    int prevVal = 0;
    int nextVal = 0;
    for(int i = limit - 1;i >= 0; --i){
        char nextChar = input.charAt(i);
        prevVal = nextVal;
        nextVal = values.get(nextChar);
        if(nextVal < prevVal){
            retVal -= nextVal;
        }else{
            retVal += nextVal;
        }
    }
    return retVal;
}

Ideally there would be validation checking required , however in this instance, the input is guaranteed to be valid.

Since there is only one loop and the Map lookup should be O(1). The complexity for this should be O(n) the length of the string.

Answer 3

By simply using an ordered map, you could arrange your keys in highest-to-lowest order, so that you can simply find the first matching prefix and take the sum from there. This way, you only need to loop over the string once.

The only secret is, that you have to be aware of java base data structures, in this case a LinkedHashMap which guarantees unmodified key order.

Working example:

// BTW: DON'T create a subclass just to init a map.
private static LinkedHashMap<String, Integer> romanSegmentToInt = new LinkedHashMap<>();
static {
    romanSegmentToInt.put("M", 1000);
    romanSegmentToInt.put("CM", 900);
    romanSegmentToInt.put("D", 500);
    romanSegmentToInt.put("CD", 400);
    romanSegmentToInt.put("C", 100);
    romanSegmentToInt.put("XC", 90);
    romanSegmentToInt.put("L", 50);
    romanSegmentToInt.put("XL", 40);
    romanSegmentToInt.put("X", 10);
    romanSegmentToInt.put("IX", 9);
    romanSegmentToInt.put("V", 5);
    romanSegmentToInt.put("IV", 4);
    romanSegmentToInt.put("I", 1);
}

public static int romanToInt(String in) {
    int sum = 0;
    while (!in.isEmpty()) {
        for (Map.Entry<String, Integer> segment : romanSegmentToInt.entrySet()) {
            if (in.startsWith(segment.getKey())) {
                sum += segment.getValue();
                in = in.substring(segment.getKey().length());
                break; // continue with outer loop
            }
        }
        // add error handling, if no prefix was found -> illegal input
    }
    return sum;
}

Answer 4

You could also use a switch statement to prevent auto-boxing. Taking the logic from @tinstaafl's solution:

class Solution {

public int romanToInt(String input){       
    int retVal = 0;
    int limit = input.length();
    int prevVal = 0;
    int nextVal = 0;
    for(int i = limit - 1;i >= 0; --i){
        char nextChar = input.charAt(i);
        prevVal = nextVal;
        switch(nextChar)
        {
            case 'I':
                nextVal = 1;
                break;
            case 'V':
                nextVal = 5;
                break;
            case 'X':
                nextVal = 10;
                break;
            case 'L':
                nextVal = 50;
                break;
            case 'C':
                nextVal = 100;
                break;
            case 'D':
                nextVal = 500;
                break;
            case 'M':
                nextVal = 1000;
                break;
            default:
                throw new RuntimeException("No valid input");
        }
        if(nextVal < prevVal){
            retVal -= nextVal;
        }else{
            retVal += nextVal;
        }
    }
    return retVal;
}
}

For those who are interested, Java generates a nice tableswitch ( with O(1) complexity) from this:

ILOAD 6
TABLESWITCH
  67: L10
  68: L11
  69: L12
  70: L12
  71: L12
  72: L12
  73: L13
  74: L12
  75: L12
  76: L14
  77: L15
  78: L12
  79: L12
  80: L12
  81: L12
  82: L12
  83: L12
  84: L12
  85: L12
  86: L16
  87: L12
  88: L17
  default: L12