Rust LeetCode: 13. Roman to Integer

Decoding Roman Numerals: Two Rust Approaches to a Classic Problem

13. Roman to Integer on LeetCode Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• 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.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Intro

Roman numerals, the numerical system of ancient Rome, have been used for centuries, from monumental Roman architecture to the pages of classical literature. Today, while our modern digital world primarily operates on the decimal system, the echoes of Roman numerals still resound in various areas, such as clock faces, book chapter titles, and annual events like the Super Bowl. Understanding and converting these numerals to integers is not just an exercise in historical linguistics but also finds its relevance in modern computing, where translating different numeral systems forms a foundational aspect of data processing and software development.

Intuition

At first glance, Roman numerals might seem straightforward, with each symbol representing a fixed value. However, the intriguing aspect lies in their lack of a positional value system, unlike our familiar decimal system where the position of a digit significantly changes its value. In Roman numerals, the value is often dictated by the sequence and combination of symbols, leading to a unique set of rules for interpretation. This absence of positional values presents an interesting challenge in designing algorithms for conversion, as one must carefully interpret the order and combination of numerals to accurately derive the corresponding integer.

Approach

In exploring the conversion of Roman numerals to integers, two distinct approaches in Rust offer insights into the language's capabilities and the trade-offs in programming styles. The imperative approach, utilizing a match statement, aligns with a straightforward, step-by-step process of decision making, echoing traditional procedural programming. It's generally easier to understand, especially for those new to Rust or programming in general. On the other hand, the functional approach, employing a HashMap, embraces Rust's powerful features in functional programming. This method shines in code readability and maintainability, especially in scenarios where the mapping might evolve or expand, offering a more scalable solution. However, it might introduce a slight overhead due to the creation and management of the HashMap.

Code

Imperative Approach with match

fn roman_to_int(s: String) -> i32 {

    let mut result = 0;
    let mut prev = 0;

    for c in s.chars() {
        let current = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            'L' => 50,
            'C' => 100,
            'D' => 500,
            'M' => 1000,
            _ => 0,
        };

        result += current;
        if current > prev {
            result -= 2 * prev
        }
        prev = current
    }
    result
}

Functional Approach using HashMap

use std::collections::HashMap;

fn roman_to_int(s: String) -> i32 {

    let translation: HashMap<char, i32> = [
        ('I', 1),
        ('V', 5),
        ('X', 10),
        ('L', 50),
        ('C', 100),
        ('D', 500),
        ('M', 1000),
    ].iter().cloned().collect();

    s.chars().enumerate().fold(0, |acc, (i, c)| {


        let current_value = translation[&c];

        if let Some(next_char) = s.chars().nth(i+1) {

            let next_value = translation[&next_char];

            if next_value > current_value {
                acc - current_value
            } else {
                acc + current_value
            }
        } else {
            acc + current_value
        }
    })
}

Explanation

To illustrate these approaches, let's consider converting "IX" to 9. In the imperative method, as we iterate through the string, we first encounter 'I' (1), followed by 'X' (10). Recognizing that 'I' is less than 'X', the algorithm adapts by subtracting twice the value of 'I' (once to negate the initial addition and once more for the actual subtraction). In the functional approach, the HashMap provides a quick lookup for each numeral's value. When processing 'I' and then 'X', the algorithm checks if the value of the next numeral ('X') is greater than the current ('I'), leading to a subtraction of 'I'. Both methods effectively capture the essence of Roman numeral logic but through different computational lenses.

Imperative Approach with match

In this approach, each Roman numeral character is converted to its integer value using a match statement. The function iterates over each character of the input string, and for each character, it checks its value and adds it to the cumulative result. If the current value is greater than the previous value (indicating a subtractive notation like IV or IX), the function subtracts twice the previous value from the result. This adjustment is necessary because the previous value was added before knowing that a subtractive notation was in use.

Functional Approach using HashMap

This version uses a HashMap to store the mappings from Roman numerals to integers. The fold function iterates over each character of the string, accumulating the total value. The lambda function inside fold checks the current and next character's value. If the next character's value is larger (indicating a subtractive combination), the current value is subtracted from the accumulator. Otherwise, it's added. The use of enumerate along with nth allows access to the current and next characters in the string.

Complexity Analysis

Time Complexity: Both implementations operate in O(n) time complexity, where n is the length of the input string. Each character is processed once in the loop.

Space Complexity: The space complexity is O(1) for both approaches, as the storage used does not grow with the size of the input. In the case of the functional approach, although a HashMap is used, its size remains constant regardless of the input.

Additional Information

• Rust's Ownership and Borrowing: Rust's ownership model ensures memory safety without a garbage collector. The functional approach demonstrates how Rust can elegantly handle data without explicit memory management.
• Idiomatic Rust: Using fold and HashMap for the functional approach is more idiomatic in Rust and showcases the language's capabilities in functional programming.
• Error Handling: Both implementations assume valid Roman numeral input. If invalid characters are possible, additional error handling would be needed.

Conclusion

Choosing between the imperative and functional approaches in Rust can depend on various factors, such as the programmer's familiarity with Rust, the specific project requirements, and the preference for a particular programming paradigm. For beginners or those preferring straightforward logic, the imperative method with match might be more appealing. Conversely, for those who appreciate the elegance and scalability of functional programming, especially in a language like Rust that excellently supports it, the HashMap approach could be more suitable. Ultimately, both methods offer valuable insights into solving problems efficiently and idiomatically in Rust.