Java - Super Easy to understand! - O(n)


  • 0
    J

    Rank each roman numeral.

    After you rank them, loop through the input and compare the current ith character with the ith-1 character.

    In particular, we compare their ranks.

    On the cases for examples when we need to convert "IV" to 4. Initally, when we see the "I", we add 1 to the current count. However, when we immediately see the "V" right after the "I", we backtrack and subtract 2(one for the count we incorrectly added and one for the conversion) from the current count and add 5. Thus, we have effectively added 4 to the current count.

    Same goes for 90("XC"). We see X, we add 10 to the current count. However, when we see "C", we know that "C"'s rank is greater than "X"'s rank. Because of this, we need to correct ourselves by subtracting 20 and adding 100. Effectively adding 90.

    public class Solution {
        public int romanToInt(String s) {
            
            HashMap<Character, Integer> rte = new HashMap<Character, Integer>();
            rte.put('I', 1);
            rte.put('V', 5);
            rte.put('X', 10);
            rte.put('L', 50);
            rte.put('C', 100);
            rte.put('D', 500);
            rte.put('M', 1000);
            
            HashMap<Character, Integer> rank = new HashMap<Character, Integer>();
            rank.put('I', 1);
            rank.put('V', 2);
            rank.put('X', 3);
            rank.put('L', 4);
            rank.put('C', 5);
            rank.put('D', 6);
            rank.put('M', 7);
            
            char last = s.charAt(0);
            int count = 0;
            
            for(int i = 0; i < s.length(); i++) {
                char current = s.charAt(i);
                
                int rankA = rank.get(last);
                int rankB = rank.get(current);
                
                if(rankA == rankB) {
                    count += rte.get(current);
                }
                else if(rankA < rankB) {
                    count -= 2*rte.get(last);
                    count += rte.get(current);
                }
                else {
                    count += rte.get(current);
                }
                
                last = current;
            }
            
            return count;
            
        }
    }
    

Log in to reply
 

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