[Java] Linear Inverted Look up

• Analysis:

• 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.

Logic:

• 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;
}
}
``````

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