Given a string representing a roman numeral , convert it into an integer.
The values of each roman character is also given:
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example,
IV means 4
XX means 20
Try out the solution here:
https://leetcode.com/problems/roman-to-integer/
Solution:
Have a look up data structure to look up the integer values for each roman symbol.
You might think of scanning through each character in the input , get their values from the look up and add them to get the integer value.
But you cannot always literally map the roman numbers to the value from the look up data structure.
If the current symbol value is less than the next symbol value , then you have to find their difference and add that to the sum , else you can add the current symbol value to the sum.
For example,
For the Roman symbol IV , we cannot look up the value for I ( equal to 1) and V (equal to 5) and add them to find the integer value ( 6).
Instead we need to find the difference of V and I values ( 5 – 1 = 4).
For other cases we can just keep adding the values from the look up.
Data Structure:
For the look up table you can use a map with a character key and an integer value.
In this example we will use a character array though.
As it is a collection of primitive data types, it occupies less memory.
Here is our look up data structure:
char[] symbolMap = new char[26];
symbolMap['I'-'A'] =1;
symbolMap['V'-'A'] =5;
symbolMap['X'-'A'] =10;
symbolMap['L'-'A'] =50;
symbolMap['C'-'A'] =100;
symbolMap['D'-'A'] =500;
symbolMap['M'-'A'] =1000;
The upper case letters are represented by ascii values from 65 to 90 in java.
Since capital A is represented by 65 subtracting the ascii value of a character with this allows us to use an array of size 26. The first element in this array then represents the character ‘A’, the second ‘B’ and so on.
Here is the left to right scan where we find the integer values of each character and its next character :
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
int value1 = symbolMap[c-'A'];
int value2 = 0;
if(i+1 < s.length()){
char n = s.charAt(i+1);
value2 = symbolMap[n-'A'];
}
if(value1 < value2){
sum += (value2 - value1);
i++;
}else{
sum+= value1;
}
}
As you see , we check for the next character if we have not reached the end of the word.
If the second character value in the lookup array is greater than the first character value , then we find the difference and add it to the sum.
Otherwise we just add the first character value to the sum.
Here is the entire code:
class Solution {
public int romanToInt(String s) {
int sum = 0;
/**
Map<Character,Integer> symbolMap = new HashMap<>();
symbolMap.put('I',1);
symbolMap.put('V',5);
symbolMap.put('X',10);
symbolMap.put('L',50);
symbolMap.put('C',100);
symbolMap.put('D',500);
symbolMap.put('M',1000);
**/
char[] symbolMap = new char[26];
symbolMap['I'-'A'] =1;
symbolMap['V'-'A'] =5;
symbolMap['X'-'A'] =10;
symbolMap['L'-'A'] =50;
symbolMap['C'-'A'] =100;
symbolMap['D'-'A'] =500;
symbolMap['M'-'A'] =1000;
for(int i=0;i<s.length();i++){
int value2 = 0;
char c = s.charAt(i);
int value1 = symbolMap[c-'A'];
if(i+1 < s.length()){
char n = s.charAt(i+1);
value2 = symbolMap[n-'A'];
}
if(value < value2){
sum += (value2 - value1);
i++;
}else{
sum+= value1;
}
}
return sum;
}
}
As already mentioned while finding the look up values we check if we have reached the end of the word or not. If not then we find the look up value for the second character as well .
Then we do the sum as follows:
sum += value2 - value1;
Notice that this is same as:
sum += value2
sum +- value1
So if we can start the scan from the right we can avoid checking if we have reached the end of the word and this will further optimize the code.
Here is the version for scanning from right to left:
class Solution {
public int romanToInt(String s) {
int sum = 0;
char[] symbolMap = new char[26];
symbolMap['I'-'A'] =1;
symbolMap['V'-'A'] =5;
symbolMap['X'-'A'] =10;
symbolMap['L'-'A'] =50;
symbolMap['C'-'A'] =100;
symbolMap['D'-'A'] =500;
symbolMap['M'-'A'] =1000;
int wordLen = s.length();
int last = symbolMap[s.charAt(wordLen-1) - 'A'];
sum += last;
for(int i=wordLen-2;i>=0;i--){
int current = symbolMap[s.charAt(i) - 'A'];
if(current < last){
sum -= current;
}else{
sum += current;
}
last = current;
}
return sum;
}
}
Time complexity:
There is a limitation as how many numbers can be represented by roman numerals.
The maximum value that can be represented by Roman symbols is 3999.
That is a constant.
So time complexity is O(1) ! in both the approaches.
Space complexity:
We are not using any extra space so space complexity is O(1) as well.
That’s it!
Leave a Reply