Roman Number to Integer and vice versa

Problem Overview

The problem "Roman to Integer" on LeetCode presents a classic example of working with numeral systems. It challenges us to convert a string representing a Roman numeral into its corresponding integer value. It can be found at LeetCode - Roman to Integer.

Problem Statement

Given a Roman numeral, convert it to an integer. Roman numerals are represented by the Latin alphabet in seven symbols: I (1), V (5), X (10), L (50), C (100), D (500), and M (1000).

Example:

• Input: "III"
• Output: 3

Roman Numeral Rules:

Roman numerals are usually written in descending order from left to right. However, a smaller numeral before a larger numeral indicates subtraction.

For example:

• IV = 4 (5 - 1)
• IX = 9 (10 - 1)
• XL = 40 (50 - 10)

Understanding the Problem

Understanding how Roman numerals work is essential for solving this problem. The key rule here involves both addition and subtraction based on numeral positioning. If a smaller numeral appears before a larger numeral, it is subtracted. If it appears after, it is added.

Detailed Steps:

• Translate each Roman numeral to its integer value.
• Traverse the Roman numeral string from left to right.
• Apply the subtraction principle, where if a numeral is smaller than the following numeral, subtract it; otherwise, add it.

Key DSA Concepts and Theory

String Traversal

The problem requires basic string manipulation techniques, primarily character-by-character traversal. This concept is crucial for inspecting and comparing characters and efficiently accumulating a result based on conditional checks.

Hash Map (or Dictionary)

Using a data structure like a hash map allows for efficient look-up times when mapping Roman numeral characters to their respective integer values, providing constant time complexity for the conversion step.

Conditional Logic

Utilizing if-else conditions helps implement the Roman numeral rules, particularly the subtraction cases.

Solution Approach

Let's break down the solution by first defining a mapping of Roman numerals to integers and then iteratively calculating the integer value from the numeral string.

C++ Solution

#include <unordered_map>
#include <string>

int romanToInt(std::string s) {
    std::unordered_map<char, int> romanMap = {
        {'I', 1}, {'V', 5},   {'X', 10}, 
        {'L', 50}, {'C', 100}, {'D', 500}, 
        {'M', 1000}
    };

    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i < s.size() - 1 && romanMap[s[i]] < romanMap[s[i + 1]]) {
            total -= romanMap[s[i]];
        } else {
            total += romanMap[s[i]];
        }
    }
    return total;
}

Java Solution

import java.util.HashMap;
import java.util.Map;

public int romanToInt(String s) {
    Map<Character, Integer> romanMap = new HashMap<>();
    romanMap.put('I', 1);
    romanMap.put('V', 5);
    romanMap.put('X', 10);
    romanMap.put('L', 50);
    romanMap.put('C', 100);
    romanMap.put('D', 500);
    romanMap.put('M', 1000);

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

Detailed Steps

1. Mapping Roman Numerals: Create a hash map to store the integer representation of Roman numerals.
2. Iterate the String: Loop through each character of the string.
3. Apply Addition or Subtraction Rule: Use a conditional to decide whether to add the numeral's value to the total or subtract it based on its position relative to the next numeral.
4. Return the Total: After looping through the string, return the computed integer value.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the Roman numeral string. Each character in the string is processed once.
• Space Complexity: O(1), since the hash map has a constant space requirement with fixed keys.

Common Mistakes to Avoid

• Ignoring Subtraction Rules: Ensure to handle cases where a smaller numeral precedes a larger numeral properly.
• Index Out of Range: When checking the next numeral, ensure not to exceed the string's bounds.

Similar Problems on LeetCode

• Integer to Roman (Question 12)
• Add Strings (Question 415)
• Valid Parenthesis String (Question 678)

Additional Resources and References

• Roman Numerals - Wikipedia
• Data Structure Analysis
• LeetCode Discussion on Roman to Integer

This article touches upon vital string manipulation techniques and the effective use of hash maps to optimize operations involving look-up tables. Understanding such patterns is essential for efficiently solving problems not only on numerals but across various data representation tasks.