13. Roman to Integer

📝 Problem Details

• Title: 13. Roman to Integer
• Link: https://leetcode.com/problems/roman-to-integer/
• Difficulty: Easy
• Tags/Categories: Hashmap

💡 Explanation of Solution

- create a hashmap where the key/value pair is:
	- key: roman numeral character
	- value: corresponding number

- initialize a sum counter
- iterate over the string

- if the current char has a lower value than the next value, then we need to decrement sum by the current value
- otherwise, increment it by the current value
- return the cumulative sum

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1) constant since we are using a fixed size hashmap

💻 Implementation of Solution

class Solution {
public:
    int romanToInt(string s) {
        //write out a hashmap that uses the symbol as the key
        //split the string into an array of chars
        //map each char to a value and add to a running total
 
        unordered_map<char, int> map = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000},
        };
 
        int sum = 0;
 
        for(int i=0; i < s.length(); i++){
            if(map[s[i]] < map[s[i+1]]){
                sum -= map[s[i]];
            }else{
                sum += map[s[i]];
            }
        }
 
        return sum;
 
    }
};