[LeetCode]#13. Roman to Integer (repeat : 0 )

Description 

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol       Value
I                   1
V                  5
X                  10
L                   50
C                  100
D                  500
M                 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

Example 1:
Input: s = "III"

Output: 3
Explanation: III = 3.

Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

---

Intuition : 

I have to consider that when the previous number is smaller than the current number ,  the previous number has to be substracted from the current number. but when the previous number is greater or equal to the current number the number has to be additional to the current number;

 

Approach : 

1) store the values in the Hashmap with key-value pair.

2) Iterate the characters of string roman number string 

3) check if the previous integer is smaller than the current integer.

4) when the previous value is smaller, simpley substract the number with the current value

 

Code : 

class Solution {
    public int romanToInt(String s) {
        
      Map<Character,Integer> m = new HashMap<>();

      m.put('I',1);
      m.put('V',5);
      m.put('X',10);
      m.put('L',50);
      m.put('C',100);
      m.put('D',500);
      m.put('M',1000);

     int answer = 0;

     for(int i=0; i<s.length(); i++){
         if(i < s.length()-1 && m.get(s.charAt(i))<m.get(s.charAt(i+1))){
             answer = answer - m.get(s.charAt(i));
         } else{
             answer = answer + m.get(s.charAt(i));
         }

     }
        
        return answer;
    }
}

Lets Say I have IV , It should return 4

The first I which is 1 will go to the if statement 

answer = answer(0) - m.get(s.charAt(0) = -1

the next V which is 5 will go to the else statement 

because i < s.length() - 1 prevents last element to be in if statement. 

therefore

answer = -1 + 5 

answer = 4

 

 

 

Performance 

Time complexity of this algorithm is O(n) where n is the number of chars in the string 

Space complexity of this algorithm is O(1) because this algorithm uses hashmap to store values of roman and integer .

 since the size of the string input does not affect the hashmap, it is considered constant space. 

 

(!!) 

I think i have to solve this n times.. even this level is considered 'easy' i couldnt solve it but look other's solutions