EasyMath

Roman to Integer

Q: Does String.replace use a regular expression?

No. replace(CharSequence, CharSequence) matches the literal text and replaces every occurrence. replaceAll is the one that treats its first argument as a regex, which is slower and makes characters such as . or $ special.

Q: Why a switch instead of a HashMap for the letter values?

A HashMap boxes the char key on every lookup and unboxes the result. The switch expression works on the primitive char, needs no allocation, and its default branch throws a clear IllegalArgumentException instead of the NullPointerException you get when map.get returns null and Java unboxes it.

Q: Why loop over toCharArray in one version and charAt in the other?

toCharArray() copies the string into a new array, which suits an enhanced for loop. charAt(i) reads in place, which suits the index loop that walks backwards. On 15 characters both are instant; charAt is the habit to keep for long strings.

Q: How do I reject a numeral that is not in standard form?

Match it first: s.matches("M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})") accepts exactly the standard numerals from 1 to 3999, plus the empty string, so check !s.isEmpty() too. IIII, VX and MMMM all fail it.

You get a string s holding a Roman numeral written in uppercase letters. Return its value as an integer. The seven letters are worth I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000.

Letters are written from largest to smallest and their values add up: CCLXII is 100 + 100 + 50 + 10 + 1 + 1 = 262. Six pairs break that order and subtract instead: a smaller letter placed directly before a larger one is taken away from it. They are IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900.

The input is always a well-formed numeral in standard form for a value from 1 to 3999, so you never have to reject an invalid string.

Examples

Input

s = "XLVII"

Output47WhyXL is the subtractive pair for 40, then V adds 5 and II adds 2: 40 + 5 + 2 = 47.

Input

s = "MCDLXXIX"

Output1479WhyM is 1000, CD is 400, LXX is 70 and IX is 9: 1000 + 400 + 70 + 9 = 1479.

Constraints

Size: 1 ≤ s.length ≤ 15
Characters: s holds only I V X L C D M
Values: 1 ≤ value ≤ 3,999
Answer: The input is always a valid numeral in standard form.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

String.replace swaps every occurrence of a literal, so six calls rewrite each subtractive pair in its additive spelling, such as IX to VIIII. The resulting string only adds, and a loop over toCharArray() sums the values from an immutable Map.of.

import java.util.*;

public class Main {
    static final Map<Character, Integer> VALUES =
        Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);

    static int romanToInt(String s) {
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
             .replace("XL", "XXXX").replace("XC", "LXXXX")
             .replace("CD", "CCCC").replace("CM", "DCCCC");
        int total = 0;
        for (char ch : s.toCharArray()) {
            total += VALUES.get(ch);
        }
        return total;
    }
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character to the first with charAt, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. The letter values come from a switch expression on the primitive char, so nothing is boxed and no new string is built.

import java.util.*;

public class Main {
    static int value(char c) {
        return switch (c) {
            case 'I' -> 1;
            case 'V' -> 5;
            case 'X' -> 10;
            case 'L' -> 50;
            case 'C' -> 100;
            case 'D' -> 500;
            case 'M' -> 1000;
            default -> throw new IllegalArgumentException("not a Roman letter: " + c);
        };
    }

    static int romanToInt(String s) {
        int total = 0;
        int prev = 0; // value of the letter to the right
        for (int i = s.length() - 1; i >= 0; i--) {
            int v = value(s.charAt(i));
            total += v < prev ? -v : v;
            prev = v;
        }
        return total;
    }
}

2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

Six chained Replace calls rewrite each subtractive pair additively (XL to XXXX, CD to CCCC), and a foreach over the result sums the letter values from a Dictionary<char, int>.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    static readonly Dictionary<char, int> Values = new()
    {
        ['I'] = 1, ['V'] = 5, ['X'] = 10, ['L'] = 50, ['C'] = 100, ['D'] = 500, ['M'] = 1000,
    };

    public static int RomanToInt(string s)
    {
        s = s.Replace("IV", "IIII").Replace("IX", "VIIII")
             .Replace("XL", "XXXX").Replace("XC", "LXXXX")
             .Replace("CD", "CCCC").Replace("CM", "DCCCC");
        int total = 0;
        foreach (char ch in s) total += Values[ch];
        return total;
    }
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character to the first, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. A switch expression maps each char to its value without a dictionary or a new string.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    static int Value(char c) => c switch
    {
        'I' => 1,
        'V' => 5,
        'X' => 10,
        'L' => 50,
        'C' => 100,
        'D' => 500,
        'M' => 1000,
        _ => throw new ArgumentException($"not a Roman letter: {c}"),
    };

    public static int RomanToInt(string s)
    {
        int total = 0;
        int prev = 0; // value of the letter to the right
        for (int i = s.Length - 1; i >= 0; i--)
        {
            int v = Value(s[i]);
            total += v < prev ? -v : v;
            prev = v;
        }
        return total;
    }
}

2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

The standard library has no replace-all for strings, so a small helper loops find and replace until the pattern is gone. Six calls rewrite the subtractive pairs additively (IX to VIIII, CM to DCCCC), and an unordered_map<char, int> sums what is left. s arrives by value, so rewriting it touches only our own copy.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        static const unordered_map<char, int> values = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000},
        };
        static const vector<pair<string, string>> spelled = {
            {"IV", "IIII"}, {"IX", "VIIII"}, {"XL", "XXXX"}, {"XC", "LXXXX"}, {"CD", "CCCC"}, {"CM", "DCCCC"},
        };
        for (const auto& [from, to] : spelled) replaceAll(s, from, to);
        int total = 0;
        for (char ch : s) total += values.at(ch);
        return total;
    }

private:
    static void replaceAll(string& s, const string& from, const string& to) {
        for (size_t pos = s.find(from); pos != string::npos; pos = s.find(from, pos + to.size())) {
            s.replace(pos, from.size(), to);
        }
    }
};

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character to the first, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. A switch maps each char to its value, so there is no hashing and no allocation.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        int total = 0;
        int prev = 0; // value of the letter to the right
        for (int i = (int)s.size() - 1; i >= 0; i--) {
            int v = value(s[i]);
            total += v < prev ? -v : v;
            prev = v;
        }
        return total;
    }

private:
    static int value(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
};

2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

C has no string replace, so do the rewrite in one scan: copy s into a malloc'ed buffer, and wherever the next two characters form a subtractive pair, write its additive spelling instead (CM becomes DCCCC). The longest spelling is five letters for two, so 5 * len / 2 + 1 bytes always fit. Then sum the buffer letter by letter and free it before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int value(char c) {
    switch (c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}

static const char* spelled(char a, char b) {
    if (a == 'I' && b == 'V') return "IIII";
    if (a == 'I' && b == 'X') return "VIIII";
    if (a == 'X' && b == 'L') return "XXXX";
    if (a == 'X' && b == 'C') return "LXXXX";
    if (a == 'C' && b == 'D') return "CCCC";
    if (a == 'C' && b == 'M') return "DCCCC";
    return NULL;
}

int romanToInt(char* s) {
    size_t len = strlen(s);
    char* buf = malloc(5 * len / 2 + 1);
    size_t n = 0;
    for (size_t i = 0; i < len; i++) {
        const char* pair = i + 1 < len ? spelled(s[i], s[i + 1]) : NULL;
        if (pair) {
            size_t k = strlen(pair);
            memcpy(buf + n, pair, k);
            n += k;
            i++; // both letters of the pair are consumed
        } else {
            buf[n++] = s[i];
        }
    }
    int total = 0;
    for (size_t i = 0; i < n; i++) total += value(buf[i]);
    free(buf);
    return total;
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character back to the first, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. A switch on the char gives the values, so the function allocates nothing and reads s exactly once.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int value(char c) {
    switch (c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}

int romanToInt(char* s) {
    int total = 0;
    int prev = 0; // value of the letter to the right
    for (size_t i = strlen(s); i-- > 0;) {
        int v = value(s[i]);
        total += v < prev ? -v : v;
        prev = v;
    }
    return total;
}

2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

Each subtractive pair has an additive spelling: IV is IIII, CM is DCCCC. Folding the six pairs over the string with str::replace returns a new String of letters that only add, and bytes().map(value).sum() adds them up.

impl Solution {
    fn value(b: u8) -> i32 {
        match b {
            b'I' => 1,
            b'V' => 5,
            b'X' => 10,
            b'L' => 50,
            b'C' => 100,
            b'D' => 500,
            b'M' => 1000,
            _ => panic!("not a Roman letter: {}", b as char),
        }
    }

    pub fn roman_to_int(s: String) -> i32 {
        const PAIRS: [(&str, &str); 6] = [
            ("IV", "IIII"), ("IX", "VIIII"), ("XL", "XXXX"),
            ("XC", "LXXXX"), ("CD", "CCCC"), ("CM", "DCCCC"),
        ];
        let additive = PAIRS.iter().fold(s, |acc, (pair, spelled)| acc.replace(pair, spelled));
        additive.bytes().map(Self::value).sum()
    }
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Iterate s.bytes().rev(), keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. Roman numerals are ASCII, so bytes are safe and cheaper than chars(), and nothing is allocated.

impl Solution {
    fn value(b: u8) -> i32 {
        match b {
            b'I' => 1,
            b'V' => 5,
            b'X' => 10,
            b'L' => 50,
            b'C' => 100,
            b'D' => 500,
            b'M' => 1000,
            _ => panic!("not a Roman letter: {}", b as char),
        }
    }

    pub fn roman_to_int(s: String) -> i32 {
        let mut total = 0;
        let mut prev = 0; // value of the letter to the right
        for b in s.bytes().rev() {
            let v = Self::value(b);
            if v < prev {
                total -= v;
            } else {
                total += v;
            }
            prev = v;
        }
        total
    }
}

FAQ for Java

Does String.replace use a regular expression?

No. replace(CharSequence, CharSequence) matches the literal text and replaces every occurrence. replaceAll is the one that treats its first argument as a regex, which is slower and makes characters such as . or $ special.

Why a switch instead of a HashMap for the letter values?

A HashMap<Character, Integer> boxes the char key on every lookup and unboxes the result. The switch expression works on the primitive char, needs no allocation, and its default branch throws a clear IllegalArgumentException instead of the NullPointerException you get when map.get returns null and Java unboxes it.

Why loop over toCharArray in one version and charAt in the other?

toCharArray() copies the string into a new array, which suits an enhanced for loop. charAt(i) reads in place, which suits the index loop that walks backwards. On 15 characters both are instant; charAt is the habit to keep for long strings.

How do I reject a numeral that is not in standard form?

Match it first: s.matches("M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})") accepts exactly the standard numerals from 1 to 3999, plus the empty string, so check !s.isEmpty() too. IIII, VX and MMMM all fail it.

Can the total overflow an int?

Not here. The largest standard numeral is worth 3999, and the running total never goes above the final value plus one subtracted letter. Even an arbitrarily long run of M would need over two million letters to pass Integer.MAX_VALUE.

Keep going

Majority Element15 / 40 · Arrays · Easy

roman_to_int.java

Java 25.0

Not run yet

+ 7 hidden

Input

s = "XLVII"

Expected

XL is the subtractive pair for 40, then V adds 5 and II adds 2: 40 + 5 + 2 = 47.