Problem Statement

You are given a string representing a Roman numeral. Your task is to convert it to an integer.

Roman Numerals Background:
Roman numerals are represented by seven different symbols:

• I : 1
• V : 5
• X : 10
• L : 50
• C : 100
• D : 500
• M : 1000

The numeral system is based on combining these symbols and applying the following rule:

• When a smaller numeral appears before a larger numeral, it is subtracted (e.g., IV = 4).
• Otherwise, the numeral values are added (e.g., VI = 6).

Example Inputs, Outputs, and Explanations

1. Example 1:

   • Input: "III"
   • Output: 3
   • Explanation: The numeral III is simply 1 + 1 + 1.

2. Example 2:

   • Input: "IV"
   • Output: 4
   • Explanation: Here, I appears before V, so it is subtracted (5 - 1).

3. Example 3:

   • Input: "MCMXCIV"
   • Output: 1994
   • Explanation:
     • M = 1000
     • CM = 900 (C before M indicates subtraction: 1000 - 100)
     • XC = 90 (X before C indicates subtraction: 100 - 10)
     • IV = 4 (I before V indicates subtraction: 5 - 1)
     • Total = 1000 + 900 + 90 + 4 = 1994

Constraints

• The input string s is guaranteed to be a valid Roman numeral.
• Typically, the length of s is in the range: 1 <= s.length <= 15.
• The string only contains the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').

Hints to Approach the Solution

1. Mapping Is Key:
   Create a dictionary (or map) that relates each Roman numeral symbol to its integer value.

2. Subtractive Notation:
   When iterating through the string, check if a numeral is less than its successor. If so, subtract it instead of adding.

Approach 1: Brute Force (Multiple Passes)

Explanation

A brute force method might involve:

• Step 1: Scan the string for subtractive pairs (like "IV", "IX", etc.) and replace them with their corresponding values.
• Step 2: Process the remaining characters individually and add their corresponding values.

Downsides

• This approach can be inefficient because you might perform multiple passes over the string.
• It complicates the handling of overlapping patterns and is more error-prone.

Pseudocode Outline

initialize total = 0
for each subtractive pair (like "IV", "IX", ...) in the numeral:
    if the pair exists in the string:
         replace it with a marker or directly add its value to total and remove it from further consideration
for each remaining character in the modified string:
    add its mapped value to total
return total

Note: While this method works, it isn’t as clean or efficient as a single-pass solution.

Approach 2: Optimal Single-Pass Solution

Explanation

This approach leverages the observation that if a smaller numeral appears before a larger numeral, you must subtract it from the total. Otherwise, add it.

Steps

1. Mapping:
   Create a dictionary mapping each Roman numeral to its integer value.
2. Iteration:
   Loop through each character in the string:
   • If the current numeral is less than the next numeral, subtract its value.
   • Otherwise, add its value.
3. Edge Handling:
   For the last numeral, simply add its value since there’s no next numeral.

Detailed Walkthrough with Example

For the numeral "MCMXCIV":

• Step 1: Create a map:

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

• Step 2: Initialize total = 0.
• Step 3: Iterate:
  • Index 0: 'M' (1000) compared to next 'C' (100) → 1000 ≥ 100 → Add 1000 → total = 1000.
  • Index 1: 'C' (100) compared to next 'M' (1000) → 100 < 1000 → Subtract 100 → total = 900.
  • Index 2: 'M' (1000) compared to next 'X' (10) → 1000 ≥ 10 → Add 1000 → total = 1900.
  • Index 3: 'X' (10) compared to next 'C' (100) → 10 < 100 → Subtract 10 → total = 1890.
  • Index 4: 'C' (100) compared to next 'I' (1) → 100 ≥ 1 → Add 100 → total = 1990.
  • Index 5: 'I' (1) compared to next 'V' (5) → 1 < 5 → Subtract 1 → total = 1989.
  • Index 6: 'V' (5) is the last character → Add 5 → total = 1994.
• Final Output: 1994

Pseudocode Outline

map = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
total = 0
for i from 0 to length(s)-1:
    if i < length(s)-1 and map[s[i]] < map[s[i+1]]:
         total -= map[s[i]]
    else:
         total += map[s[i]]
return total

Code Implementations

Python Code