Table based solution that simplifies the encoding


  • 0
    A

    Here is a simple table based solution to the problem:

    Comments welcome!

    /**
     * below are the basic characters of the vocab are
         I - 1
         II - 2
         III - 3
         IV - 4
         V - 5
         VI - 6
         VII - 7
         VIII - 8
         IX - 9
         X - 10
         XL - 40
         L - 50
         XC - 90
         C - 100
         CD - 400
         D - 500
         CM - 900
         M - 1000
     
     start from right of srting - 
        keep going consuming as long as you find the characters in the table above - greedy, for that substring add the corresponding number to total 
        return total.
     
    **/
    
    class Solution {
        public Map<String, Integer> buildBasicMapping(Map<String, Integer> table){
            table.put("I",1);
            table.put("II", 2);
            table.put("III", 3);
            table.put("IV", 4);
            table.put("V", 5);
            table.put("VI", 6);
            table.put("VII", 7);
            table.put("VIII",8);
            table.put("IX",9);
            table.put("X", 10);
            table.put("XL", 40);
            table.put("L", 50);
            table.put("XC", 90);
            table.put("C", 100);
            table.put("CD", 400);
            table.put("D", 500);
            table.put("CM", 900);
            table.put("M", 1000);
            
            return table;
        }
        public int romanToInt(String s) {
            Map<String, Integer> rToN = new HashMap<String, Integer>();
            int total = 0;
            rToN = buildBasicMapping(rToN);
            for (int i = s.length() -1, prev = s.length(); i >= 0; i--){
                if (rToN.containsKey(s.substring(i, prev))){
                    if(i == 0 || !rToN.containsKey(s.substring(i-1, prev))){
                        //The next char is not a valid contiguous string.
                        String key = s.substring(i, prev);
                        total += rToN.get(key);
                        prev = i;
                    }else{
                        //greedily keep consuming
                    }
                }else{
                    //If the current string is not found - the
                }
                
            }
            return total;
            
        }
    }
    
    

Log in to reply
 

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