Simple O(n) solution with single traversal with easy to understand explanation


  • 2
    R

    The simple idea is to traverse the String from right to left. The basic symbols and corresponding integer values are pre populated into HashMap. We keep a variable called sum to obtain the final answer.

    Now we traverse the string from right to left, fetch the value for corresponding character. if the current value is lesser than the previous value, we subtract it from the sum, else we add it to the sum and continue to traverse the entire string.

    public int romanToInt(String s) {
            if(s == null){
                return 0;
            }
            
            HashMap<Character,Integer> map = new HashMap();
            map.put('I',1);
            map.put('V',5);
            map.put('X',10);
            map.put('L',50);
            map.put('C',100);
            map.put('D',500);
            map.put('M',1000);
            
            
            int sum = 0;
            int prev = -1;
            for(int i=s.length()-1;i>=0;i--){
                int value = map.get(s.charAt(i));
                if(value < prev){
                    sum = sum - value;
                }else{
                    sum = sum + value;
                }
                prev = value;
            }
            
            return sum;
        }
    

Log in to reply
 

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