Leetcode 13 - Roman To Int | av Aditya Dedhia

1 week, 5 days ago - macroblocks · 1 min lesning

LeetCode 13 - Roman to Int

Topics: 💻 cs🏷️ problem📚 leetcode😊 easy

Intuition

The obvious approach is to iterate through the string and sum up the values of each Roman numeral symbol. To handle subtraction cases, we could treat each as a conditional check. However, the key insight is that we can handle these cases retroactively: when we encounter a larger value after a smaller one, we've already added the smaller value, so we need to subtract it twice (once to cancel the addition, once for the actual subtraction).

Approach

1. Create a mapping of Roman symbols to their integer values

2. Iterate through each character in the string, tracking the previous symbol

3. For each character:

If the previous symbol's value is less than the current symbol's value, this indicates a subtraction case (IV, IX, XL, XC, CD, CM)
Subtract the previous value twice: once to undo the previous addition, and once to apply the subtraction rule
Add the current character's value to the sum

📝 noteWhilst it is technically possible for symbols like D to appear before M, they would not be considered valid roman numerals, which the problem guarantees as its constraint, hence, this approach works. Without this constraint, we would need to explicitly check for the six valid subtraction pairs.

Complexity

Time complexity: O(n)

We iterate through the string once, performing constant-time operations for each character.

Space complexity: O(1)

We use a fixed-size dictionary (7 entries) and a few variables, regardless of input size.

Solution

Both solutions are optimal

1. Brute Force

class Solution:

def romanToInt(self, s: str) → int:

current_sum: int = 0

previous_symbol: str = ""

symbol_to_key: dict[str, int] = {

"I": 1,

"V": 5,

"X": 10,

"L": 50,

"C": 100,

"D": 500,

"M": 1000

}

for char in s:

char_value = symbol_to_key[char]

revised_char_value = char_value

if previous_symbol = "I" and char = "V":

revised_char_value = 3 # -1 + 4 = 3

if previous_symbol = "I" and char ="X":

revised_char_value = 8 # -1 + 9 = 8

if previous_symbol = "X" and char = "L":

revised_char_value = 30 # -10 + 40 = 30

if previous_symbol = "X" and char = "C":

revised_char_value = 80 # -10 + 90 = 80

if previous_symbol = "C" and char = "D":

revised_char_value = 300 # - 100 + 400

if previous_symbol = "C" and char = "M":

revised_char_value = 800 # - 100 + 900

current_sum += revised_char_value

previous_symbol = char

return current_sum

2. Concise

class Solution:

def romanToInt(self, s: str) → int:

previous_symbol: str = ""
current_sum: int = 0

symbol_values: dict[str, int] = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}

for char in s:
char_value: int = symbol_values[char]
previous_value = None

if previous_symbol:
previous_value = symbol_values[previous_symbol]

if previous_value and previous_value < char_value:
current_sum -= previous_value * 2

current_sum += char_value
previous_symbol = char

return current_sum

blokker

tråddiskusjon