[Java] Linear Inverted Look up

  • 0


    • Each decimal digit has specific string pattern in Roman. based on power.
    • Example: 2= II; 20=XX; 200=CCC; So the same digit '2' has specific roman equivalent string in roman, depending on its decimal power.


    • Scan the string from left to right, until it is empty.
    • Look for powers from highest power possible. In our problem its THOUSANDS.
    • Look for digit from 9 to 1.
    • for every matching digit, find the true value of the digit and add it to result.
    • remove the matching string from input, and repeat.
    class Solution {
        // W = 5000, H = 10k. Just for fill the search structure.
        // Here is no digit required for ZERO. Hence "?" is used to fill the space.
        String digit[][] = {
            {"?", "I", "II", "III", "IV", "V", "VI", "VII", "VIII",  "IX"},
            {"?", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
            {"?", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
            {"?", "M", "MM", "MMM", "MW", "W", "WM", "WMM", "WMMM", "MH"}
        public int romanToInt(String s) {
            int result = 0;
            // The solution always converges. Hence a linear inverse check would work.
            for (int i=3; i>=0; i--) {  // powers of 10.  When i =3, it represents digits for thousands.
                for (int d=9;d>0; d--) { // digit
                    if (s.startsWith(digit[i][d])) {
                        int num = (Math.toIntExact(Math.round(Math.pow(10, i))) * d;
                        result += num;
                        s = s.substring(digit[i][d].length());
                        break;  // No more digits will be found at sa
            return result;

Log in to reply

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