# [LeetCode] 
Top Interview 150 Problems Solving # 13 Roman to Integer

# Understanding the **Problem**

The problem is direct and very simply understandable. Changing roman number to integer and returning the integer is the only task.

But it is quite tricky when it comes to the combination of the numbers.

```python
# basic roman numbers
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
```

The tricks that I had checked from the instruction was three.

* `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.
    

# Approach

Hash map was the solution that I had thought about. I would build the hash map for the basic roman numbers for the single characters, then another hash map for the combinations.

```python
# combination
nums = {
    "IV":4,
    "IX":9,
    "XL":40,
    "XC":90,
    "CD":400,
    "CM":900
}

# single characters
symbols = {
    "I":1,
    "V":5,
    "X":10,
    "L":50,
    "C":100,
    "D":500,
    "M":1000
}
```

With the two hash maps, I would just need to `for` loop.

# **Solution**

```python
class Solution:
    def romanToInt(self, s: str) -> int:
        nums = {
            "IV":4,
            "IX":9,
            "XL":40,
            "XC":90,
            "CD":400,
            "CM":900
        }

        symbols = {
            "I":1,
            "V":5,
            "X":10,
            "L":50,
            "C":100,
            "D":500,
            "M":1000
        }

        total = 0
        # checking subtracts
        for k, v in nums.items():
            while k in s:
                s = s.replace(k, "")
                total += v
        
        # replacing single nums
        for c in s:
            total += symbols[c]
        return total
```

I was using `total` to get the sum from the roman numbers.

1. First thing was to get key as `k` and value as `v` from `nums` for the combination calculation while iterating the hash map, then check in the `while` loop the `k`. If it includes the `k`, value(`v`) will be added to total and replace the key so it will not be again used to calculate integer.
    
2. In another `for` loop in the `s`, just as simple as that, I check each character(`c`) then add the corresponding number to `total`
    
3. Just returned total as integer
    

# **Reflection**

This was somehow not as hard as I thought it would be. But if I have to think about the efficiency, it is not as good as it should be(still better than many others on LeetCode). The complexity will go nearly *O(2n²)*. Others did it with *O(n)*, looping with only one time `for` char by char, comparing current index value with the previous value. Well, this is some rule that I did not know of. Something new to learn today as well.